title: Applying Fast Fourier transform with a specific product function
body: <p><strong>Problem:</strong> Given <code>2N</code> degree polynomials as <code>a<sub>0</sub>+a<sub>1</sub>x+a<sub>2</sub>x<sup>2</sup>..+a<sub>N</sub>x<sup>N</sup></code> and
  <code>b<sub>0</sub>+b<sub>1</sub>x+b<sub>2</sub>x<sup>2</sup>..+b<sub>N</sub>x<sup>N</sup></code>. Assume no 2 coefficient are the same in the 2 polynomials.</p>
  
  <p>Find the product of the polynomials, the catch is that the product(*) operator between the coefficients is defined differently:</p>
  
  <p><code>f(i,j) := a<sub>i</sub> * b<sub>j</sub> := 1/abs(a<sub>i</sub>-b<sub>j</sub>)</code></p>
  
  <p>That means, find the following polynomial:</p>
  
  <p><code>c<sub>0</sub>+c<sub>1</sub>x+c<sub>2</sub>x<sup>2</sup>..+c<sub>2N</sub>x<sup>2N</sup></code>,</p>
  
  <p>where</p>
  
  <p><code>c<sub>k</sub> := Σ<sub>i=0..N</sub> f(i,k-i)</code></p>
  
  <p>I know that with FFT, 2 polynomials can be multiplied in <code>O(n lg n)</code> time with normal product operator between the coefficients but don't have any idea for this kind of problem.</p>