http://acm.hdu.edu.cn/showproblem.php?pid=1402
我的代码，由于时间的问题，以后找机会优化了！（超时）
View Code
#include"iostream"
#define M 100010
using namespace std;
char ch1[M],ch2[M];
int a[M],b[M];
int c[M],d[M];
int num[M];
int H[M];
int t,k,g,v;
int i,j;
int La,Lb;
int sign=0;
void Add(int x ,int y)
{
sign=0; t=0;
int p,q,flag=0;
if(x>y)
{
for(p=0,q=0;p<y,q<y; p++,q++)
{
num[t++]=(d[p]+H[q]+flag)%10;
flag=(d[p]+H[q]+flag)%10;
}
for(p=y; p<x ; p++)
{
num[t++]=(d[p]+flag)%10;
flag=(d[p]+flag)/10;
}
}
else if(x==y)
{
for(p=0,q=0;p<x,q<y; p++,q++)
{
num[t++]=(d[p]+H[q]+flag)%10;
flag=(d[p]+H[q]+flag)/10;
}
}
else
{
flag=0;
for(p=0,q=0;p<x,q<x; p++,q++)
{
num[t++]=(H[p]+d[q]+flag)%10;
flag=(H[p]+d[q]+flag)/10;
}
for(q=x;q<y;q++)
{
num[t++]=(H[q]+flag)%10;
flag=(H[q]+flag)/10;
}
}
while(flag)
{
num[t++]=flag%10;
flag/=10;
}
for(int yy=0; yy<t;yy++)
{
d[yy]=num[yy];
if(d[yy]==0) sign++; //sign用于标记都为结果0的情况
}
g=t;
memset(H , 0 , sizeof(H));
memset(num, 0, sizeof(num));
}
void BigN()
{
int flag=0;
int mark=0;
if(La>Lb)
{
for(i=Lb-1;i>=0;i--)
{
k=0;
for(j=La-1;j>=0;j--)
{
c[k++]=(b[i]*a[j]+flag)%10;
flag=(b[i]*a[j]+flag)/10;
}
while(flag)
{
c[k++]=flag%10;
flag/=10;
}
//末尾赋值0
v=0;
for(int xx=0; xx<mark; xx++)
H[v++]=0;
for(int m=0;m<k;m++)
H[v++]=c[m];
memset(c,0,sizeof(c));
//****************************
Add(g , v);
mark++;
}
}
else
{
for(i=La-1;i>=0;i--)
{
k=0;
for(j=Lb-1;j>=0;j--)
{
c[k++]=(a[i]*b[j]+flag)%10;
flag=(a[i]*b[j]+flag)/10;
}
while(flag)
{
c[k++]=flag%10;
flag/=10;
}
//末尾赋值0
v=0;
for(int xx=0; xx<mark; xx++)
H[v++]=0;
for(int m=0;m<k;m++)
H[v++]=c[m];
//****************************
Add(g , v);
mark++;
}
}
}
int main()
{
while(cin>>ch1>>ch2)
{
t=0;k=0;g=0;
La=strlen(ch1);
Lb=strlen(ch2);
for(i=0;i<La;i++) a[i]=ch1[i]-'0';
for(i=0;i<Lb;i++) b[i]=ch2[i]-'0';
BigN();
if(sign!=t)
{
for(i=t-1;i>=0;i--)
cout<<d[i];
cout<<endl;
}
else cout<<"0"<<endl;
}
return 0;
}
一位dn的，神人啊！
http://www.cppblog.com/misschuer/archive/2010/01/16/80356.html
View Code
#include<iostream>
#include<cmath>
using namespace std;
typedef struct vir{
double re,im;
vir(){}
vir(double a,double b){re=a;im=b;}
vir operator +(const vir &b){ return vir(re+b.re,im+b.im);}
vir operator -(const vir &b){ return vir(re-b.re,im-b.im);}
vir operator *(const vir &b){ return vir(re*b.re-im*b.im,re*b.im+b.re*im);}
}vir;
vir x1[200005],x2[200005];
const double Pi = acos(-1.0);
void change(vir *x,int len,int loglen)
{
int i,j,k,t;
for(i=0;i<len;i++)
{
t = i;
for(j=k=0;j<loglen;j++,t>>=1)
k = (k<<1)|(t&1);
if(k<i)
{
vir wt = x[k];
x[k] = x[i];
x[i] = wt;
}
}
}
void fft(vir *x,int len,int loglen)
{
int i,j,t,s,e;
change(x,len,loglen);
t = 1;
for(i=0;i<loglen;i++,t<<=1)
{
s = 0;
e = s + t;
while(s<len)
{
vir a,b,wo(cos(Pi/t),sin(Pi/t)),wn(1,0);
for(j=s;j<s+t;j++)
{
a = x[j];
b = x[j+t]*wn;
x[j] = a + b;
x[j+t] = a - b;
wn =wn*wo;
}
s = e+t;
e = s+t;
}
}
}
void dit_fft(vir *x,int len,int loglen)
{
int i,j,s,e,t=1<<loglen;
for(i=0;i<loglen;i++)
{
t>>=1;
s=0;
e=s+t;
while(s<len)
{
vir a,b,wn(1,0),wo(cos(Pi/t),-sin(Pi/t));
for(j=s;j<s+t;j++)
{
a = x[j]+x[j+t];
b = (x[j]-x[j+t])*wn;
x[j] = a;
x[j+t] = b;
wn = wn*wo;
}
s = e+t;
e = s+t;
}
}
change(x,len,loglen);
for(i=0;i<len;i++)
x[i].re/=len;
}
int main()
{
char a[100005],b[100005];
int i,len1,len2,t,over,len,loglen;
while(scanf("%s%s",a,b)!=EOF)
{
len1 = strlen(a)<<1;
len2 = strlen(b)<<1;
len = 1;
loglen = 0;
while(len<len1)
{
len<<=1;
loglen++;
}
while(len<len2)
{
len<<=1;
loglen++;
}
for(i=0;a[i]!='\0';i++)
{
x1[i].re = a[i]-'0';
x1[i].im = 0;
}
for(;i<len;i++)
x1[i].re = x1[i].im = 0;
for(i=0;b[i]!='\0';i++)
{
x2[i].re = b[i]-'0';
x2[i].im = 0;
}
for(;i<len;i++)
x2[i].re = x2[i].im = 0;
fft(x1,len,loglen);
fft(x2,len,loglen);
for(i=0;i<len;i++)
x1[i] = x1[i]*x2[i];
dit_fft(x1,len,loglen);
for(i=(len1+len2)/2-2,over=loglen=0;i>=0;i--)
{
t = x1[i].re + over + 0.5;
a[loglen++] = t%10;
over = t/10;
}
while(over)
{
a[loglen++] = over%10;
over /= 10;
}
for(loglen--;loglen>=0&&!a[loglen];loglen--);
if(loglen<0)
putchar('0');
else
for(;loglen>=0;loglen--)
putchar(a[loglen]+'0');
putchar('\n');
}
return 0;
}