[模板] 大数相乘模板
发布时间:2020-12-14 03:04:58 所属栏目:大数据 来源:网络整理
导读:普通版本 要求不高的时候可以用,时间虽长但代码短。 #includeiostream#includecstring#includecstdiousing namespace std;char n[1000],m[1000];int re[2000];int cal(char *n,char *m){ int n_len = strlen(n) - 1; int m_len = strlen(m) - 1; memset(re,
要求不高的时候可以用,时间虽长但代码短。 #include<iostream> #include<cstring> #include<cstdio> using namespace std; char n[1000],m[1000]; int re[2000]; int cal(char *n,char *m) { int n_len = strlen(n) - 1; int m_len = strlen(m) - 1; memset(re,sizeof(re)); for (int i = m_len; i >= 0; i--) { for (int j = n_len; j >= 0; j--) { int idx = m_len-i + n_len-j; re[idx] += (n[j]-48) * (m[i]-48); if (re[idx] > 9) { re[idx+1] += re[idx] / 10; re[idx] %= 10; } } } int i = strlen(n) + strlen(m); while (re[i] == 0) i--; return i; } int main() { while (~scanf("%s%s",n,m)) { int i = cal(n,m); while (i >= 0) printf("%d",re[i--]); putchar(10); } return 0; }
#include<iostream> #include<cstdio> #include<cmath> using namespace std; #define MAXN 1000 #define pi acos(-1.0) struct digt { double r; double i; }; digt bitRecv[2*MAXN]; digt va[MAXN*2],vb[2*MAXN]; int ans[MAXN*2]; digt digt_Add(digt a,digt b) { digt t; t.r = a.r+b.r; t.i = a.i+b.i; return t; } digt digt_Sub(digt a,digt b) { digt t; t.r = a.r-b.r; t.i = a.i-b.i; return t; } digt digt_Multi(digt a,digt b) { digt t; t.r = a.r*b.r - a.i*b.i; t.i = a.r*b.i + a.i*b.r; return t; } int rev(int x,int len) //位反置:翻转二进制前len位 { int sum = 0; while (len--) { sum <<= 1; sum |= (x&1); x >>= 1; } return sum; } void bitRevCpy(digt *a,int len) { int bits = 0,t = 1; while (t < len) //计算位长度 { bits++; t <<= 1; } for (int i = 0; i < len; i++) bitRecv[rev(i,bits)] = a[i]; for (int i = 0; i < len; i++) a[i] = bitRecv[i]; } void FFT(digt *Fourier,int len,int on) { int loop,m; digt wm,w; bitRevCpy(Fourier,len); //利用位反置生成输入序列 for (loop = 2; loop <= len; loop <<= 1) { m = loop; //分治后计算长度为m的DFT wm.r = cos(on*2*pi/m); wm.i = sin(on*2*pi/m); //这次单位复根 e^(2*pi/m) 用欧拉公式展开 for (int k = 0; k < len; k += m) //FFT过程 { w.r = 1; w.i = 0; //旋转因子 for (int j = 0; j < m/2; j++) { digt t = digt_Multi(w,Fourier[k+j+m/2]); digt u = Fourier[k+j]; Fourier[k+j] = digt_Add(u,t); Fourier[k+j+m/2] = digt_Sub(u,t); //蝴蝶操作合并 w = digt_Multi(w,wm); //更新旋转因子 } } } if (on == -1) { for (int i = 0; i < len; i++) Fourier[i].r = Fourier[i].r/len; //IDFT } } void conv(digt *a,digt *b,int len) //求卷积 { FFT(a,len,1); FFT(b,1); for (int i = 0; i < len; i++) a[i] = digt_Multi(a[i],b[i]); FFT(a,-1); } int cal(char *n,char *m) // 返回结果的位数 { int i; int n_len = strlen(n); int m_len = strlen(m); int re_len = 1; while (re_len < n_len*2 || re_len < m_len*2 ) re_len <<= 1; for(i = 0; i < re_len; i++) va[i].i = vb[i].i = 0; for (i = 0; n[i]; i++) va[i].r = n[n_len-i-1]-'0'; while (i < re_len) va[i++].r = 0; for (i = 0; m[i]; i++) vb[i].r = m[m_len-i-1]-'0'; while (i < re_len) vb[i++].r = 0; conv(va,vb,re_len); //FFT卷积相当于不进位乘法 for (i = 0; i < re_len; i++) ans[i] = int(va[i].r + 0.5); for (i = 0; i < re_len; i++) { ans[i+1] += ans[i]/10; ans[i] %= 10; } int idx; for (idx = n_len+m_len-1; idx && ans[idx] <= 0; idx--); return idx; } int main() { char n[MAXN*2],m[MAXN*2]; while (~scanf("%s%s",m)) { int len = cal(n,m); while(len >= 0) printf("%d",ans[len--]); putchar(10); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |