#include #include "misc.h" #include "fft.h" C it(C w){C r; __real__ r = - __imag__ w; __imag__ r = __real__ w; return r;} C Sqrt(C x){ R A = __real__ x, B = __imag__ x; if(A < 0) return it(Sqrt(-x)); {R r = sqrt((A + sqrt(A*A + B*B))/2); return r + it(B/(2*r));}} void fft(c a[], const int n){ {int j=0; for(int i=0; i