代码如下
int FGE2(int n) { int temp = n - 1; temp |= temp >> 1; temp |= temp >> 2; temp |= temp >> 4; temp |= temp >> 8; temp |= temp >> 16; //temp |= temp >> 32; //如果类型是long long return temp + 1; } 大数FFT我们以大数$abcdef$为例，$f(x)=f+ex+dx^2+cx^3+bx^4+ax^5+0x^6+0x^7$,则$f(10)=abcdef$
我们以$21\times 34$为例：
$$f(x)=1+2x+0x^2+0x^3$$
$$g(x)=4+3x+0x^2+0x^3$$
$$h(x)=f(x)g(x)=4+11x+6x^2+0x^3$$
$$(1+2x)(4+3x)=4+11x+6x^2$$
$$x=10,~21\times 34=4+110+600=714$$
实际中，将多项式系数进位就可以得到。例如将11进位，将1加到6，得到4，1，7。
例题HDU 1402
#include <iostream> #include <algorithm> #include <complex> #include <cstring> using namespace std; double pi = acos(-1); complex<double> A[131072], B[131072]; int answer[131072]; char sa[50000], sb[50000]; unsigned int rev32bit(unsigned int x) { x = ((x & 0x55555555) << 1) | ((x & 0xaaaaaaaa) >> 1); x = ((x & 0x33333333) << 2) | ((x & 0xcccccccc) >> 2); x = ((x & 0x0f0f0f0f) << 4) | ((x & 0xf0f0f0f0) >> 4); x = ((x & 0x00ff00ff) << 8) | ((x & 0xff00ff00) >> 8); x = ((x & 0x0000ffff) << 16) | ((x & 0xffff0000) >> 16); return x; } void FFT(complex<double>* a, int n, int inv) { int bit = 0; while ((1 << bit) < n) bit++; for (int i = 0; i < n; i++) { int temp = rev32bit(i) >> (32 - (bit)); if (i < temp) swap(a[i], a[temp]); } for (int mid = 1; mid < n; mid *= 2) { complex<double> w(cos(pi / mid), inv * sin(pi / mid)); for (int i = 0; i < n; i += mid * 2) { complex<double> temp = 1; for (int j = 0; j < mid; j++, temp *= w) { //complex<double> w(cos(pi * j / mid), inv * sin(pi * j / mid)); complex<double> l = a[i + j]; complex<double> r = temp * a[i + j + mid]; a[i + j] = l + r; a[i + j + mid] = l - r; } } } } int FGE2(int n) { int temp = n - 1; temp |= temp >> 1; temp |= temp >> 2; temp |= temp >> 4; temp |= temp >> 8; return temp + 1; } int main(int argc, char* argv[]) { while (~scanf("%s%s", sa, sb)) { int len1 = strlen(sa); int len2 = strlen(sb); int len = FGE2(max(len1, len2)) * 2; for (int i = 0; i < len1; i++) A[i] = sa[len1 - i - 1] - '0'; for (int i = len1; i < len; i++) A[i] = 0; for (int i = 0; i < len2; i++) B[i] = sb[len2 - i - 1] - '0'; for (int i = len2; i < len; i++) B[i] = 0; FFT(A, len, 1); FFT(B, len, 1); for (int i = 0; i < len; i++) { A[i] = A[i] * B[i]; } FFT(A, len, -1); for (int i = 0; i < len; i++) { answer[i] = (int)(A[i].real() / len + 0.5); } for (int i = 0; i < len - 1; i++) { answer[i + 1] += answer[i] / 10; answer[i] %= 10; } int index; for (index = len - 1; index > 0; index--) { if (answer[index] != 0) break; } for (int i = index; i >= 0; i--) { printf("%d", answer[i]); } printf("\n"); } return 0; }洛谷 P1919
只需要将数组大小改成2097152和1000000即可。