题意
实现两个大整数的加法
思路
整数加法可以看成多项式加法，然后就可以利用FFT通过进行卷积计算的方法来实现。
浮点数误差不会卡掉这个题。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; #pragma mark - Fast Fourier Transformation(FFT()) and Convolution Calaulation(Convolution()) const double PI = acos(-1.0); typedef complex<double> Complex; void FFT_Rader(Complex *F,int len){ //BIT-REVERSE-COPY() 倒位序重新排列数组 int j = len >> 1; for (int i = 1; i < len - 1; i++) { if (i < j) { swap(F[i], F[j]); } int k = len >> 1; while (j >= k) { j -= k; k >>= 1; } if (j < k) { j += k; } } } void FFT(Complex *F,int len,int on){ //on是方向标记，当on为1时，执行FFT，时域->频域；当on为-1时，执行IFFT，频域->时域 FFT_Rader(F, len); //把F数组倒位序处理 for (int h = 2; h <= len; h <<= 1) { //分治后当前DFT的长度为h(不是使用阶段表示) Complex wn(cos(-on * 2 * PI / h),sin(-on * 2 * PI / h)); //使用欧拉定理展开复数单位根 for (int j = 0; j < len; j += h) { //向量树上节点对应开始区段 Complex w(1,0); //旋转因子 for (int k = j; k < j + h / 2; k++) { Complex u = F[k]; Complex t = w * F[k + h / 2]; F[k] = u + t; //蝶形操作合并 F[k + h /2] = u - t; //DFT的对称性 w = w * wn; //更新旋转因子 } } } if (on == -1) { //IFFT在sigma外面要除以N(DFT长度) for (int i = 0; i < len; i++) { F[i] /= len; } } } void Convolution(Complex *a,Complex *b,int len){ //卷积定理:FFT(a卷b)=FFT(a)*FFT(b) //a和b的长度必须统合一致，不足的用0补齐 //长度必须是2的整数次幂 //将会直接用a向量来接受卷积结果，两个向量都会被破坏 FFT(a, len, 1); FFT(b, len, 1); for (int i = 0; i < len; i++) { a[i] *= b[i]; } FFT(a, len, -1); } #pragma mark - const int MAXN = 500005; Complex A[MAXN],B[MAXN]; char sa[MAXN],sb[MAXN]; int res[MAXN]; int prepare(char *a,char *b){ int lena = (int)strlen(a); int lenb = (int)strlen(b); int len = 1; while (len < 2*lena || len < 2*lenb) { len <<= 1; } for (int i = 0; i < len; i++) { A[i].real(0); B[i].real(0); if (i < lena) { A[i].real(sa[lena-i-1]-'0'); } if (i < lenb) { B[i].real(sb[lenb-i-1]-'0'); } A[i].imag(0); B[i].imag(0); } return len; } void solve(){ memset(res, 0, sizeof(res)); int len = prepare(sa, sb); Convolution(A, B, len); for (int i = 0; i < len; i++) { A[i] += 0.5; //规避浮点误差 res[i] = A[i].real(); } int bound = 0; for (int i = 0; i < len; i++) { res[i+1] += res[i] / 10; res[i] %= 10; } for (int i = len - 1; i >= 0; i--) { if (res[i]) { bound = i; break; } } for (int i = bound; i >= 0; i--) { printf("%d",res[i]); } putchar('\n'); } int main(){ while (scanf(" %s %s",sa,sb) != EOF) { solve(); } return 0; } |
