大数相乘快速傅立叶变换法 c++ 源码

#include 
#include 
#include 
#include 
using namespace std;

const long double PI = 3.1415926535897932384626433832795L;

int BitRev（int x int n）
{	int res = 0;
	for （; n != 1; n /= 2）
	{	res = res*2+x%2;
		x /= 2;
	}
	return res;
}

void FFT（complex x[] int n）
{	int ijkt;
	for （i = 0; i < n; ++i）
	{	j = 0;
		for （t = i k = n; k /= 2; t /= 2）
			j = j*2+t%2;
		if （j > i） swap（x[j] x[i]）;
	}
	for （k = 2; k <= n; k *= 2）
	{	const complex omega_unit（cosl（2*PI/k） sinl（2*PI/k））;
		for （i = 0; i < n; i += k）
		{	complex omega（1 0）;
			for （j = 0; j < k/2; ++j）
			{	complex t = omega*x[i+j+k/2];
				x[i+j+k/2] = x[i+j]-t;
				x[i+j] += t;
				omega *= omega_unit;
			}