hdu 1402 A * B Problem Plus (FFT + 大数相乘)
发布时间:2020-12-14 02:49:37 所属栏目:大数据 来源:网络整理
导读:A * B Problem Plus Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 13456????Accepted Submission(s): 2401 Problem Description Calculate A * B. ? Input Each line will contain two integ
A * B Problem PlusTime Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 13456????Accepted Submission(s): 2401
Problem Description
Calculate A * B.
?
Input
Each line will contain two integers A and B. Process to end of file.
Note: the length of each integer will not exceed 50000.
?
Output
For each case,output A * B in one line.
?
Sample Input
?
Sample Output
?
干完这题,对FFT有了点感觉。 #include <iostream> #include <string> #include <cstdio> #include <cstring> #include <cmath> using namespace std; const double pi=acos(-1.0); const int maxn=50010; struct Complex { double a,b; Complex(){} Complex(double _a,double _b):a(_a),b(_b){} Complex operator + (const Complex &c) { return Complex(a+c.a,b+c.b); } Complex operator - (const Complex &c) { return Complex(a-c.a,b-c.b); } Complex operator * (const Complex &c) { return Complex(a*c.a-b*c.b,a*c.b+b*c.a); } }num1[maxn*4],num2[maxn*4]; string str1,str2; int cnt,ans[maxn*4]; void ready() { cnt=1; int len1=str1.size(),len2=str2.size(); while(cnt<2*len1 || cnt<2*len2) cnt<<=1; for(int i=len1-1,j=0;i>=0;i--,j++) num1[j]=Complex(str1[i]-'0',0); for(int i=len1;i<=cnt;i++) num1[i]=Complex(0,0); for(int i=len2-1,j++) num2[j]=Complex(str2[i]-'0',0); for(int i=len2;i<=cnt;i++) num2[i]=Complex(0,0); } void change(Complex s[],int len) { for(int i=1,j=len/2;i<len-1;i++) { if(i<j) swap(s[i],s[j]); int k=len/2; while(j>=k) { j-=k; k/=2; } if(j<k) j+=k; } } void FFT(Complex s[],int len,int on) { change(s,len); for(int i=2;i<=len;i<<=1) { Complex wn=Complex(cos(-on*2*pi/i),sin(-on*2*pi/i)); for(int j=0;j<len;j+=i) { Complex w(1,0); for(int k=j;k<j+i/2;k++) { Complex u=s[k]; Complex t=w*s[k+i/2]; s[k]=u+t; s[k+i/2]=u-t; w=w*wn; } } } if(on==-1) { for(int i=0;i<len;i++) s[i].a/=len; } } void deal() { FFT(num1,cnt,1); FFT(num2,1); for(int i=0;i<cnt;i++) num1[i]=num1[i]*num2[i]; FFT(num1,-1); } void solve() { for(int i=0;i<cnt;i++) ans[i]=(int)(num1[i].a+0.5); for(int i=0;i<cnt;i++) { ans[i+1]=ans[i+1]+ans[i]/10; ans[i]=ans[i]%10; } cnt=str1.size()+str2.size()-1; while(ans[cnt]==0 && cnt>0) cnt--; for(int i=cnt;i>=0;i--) putchar(ans[i]+'0'); putchar('n'); } int main() { while(cin>>str1>>str2) { ready(); deal(); solve(); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |