题目描述 Description
给出两个正整数A和B，计算A*B的值。保证A和B的位数不超过100000位。
输入描述 Input Description
读入两个用空格隔开的正整数
输出描述 Output Description
输出A*B的值
样例输入 Sample Input
4 9
样例输出 Sample Output
36
数据范围及提示 Data Size & Hint
两个正整数的位数不超过100000位
什么都不说了，裸FFT
看了一天的算导，勉强看懂了怎么O(nlogn)求dft，求dft^(-1)就实在看不懂了，唉，只好记下结论
首先是理解系数表达和点值表达，因为点值表达乘法是O（n）的，所以我们要通过系数表达算出点值表达，相乘后再算出点值表达
这个是分治求的dft奇偶分成两个序列，分别求出这两个序列的dft然后通过下面的代码就可以O（n）合并这个两个dft了
for i:= to n>>(t+)- do
begin
p:=i<<(t+)+s;
wt:=w[i<<t]*a[p+<<t];
tt[i]:=a[p]+wt;
tt[i+n>>(t+)]:=a[p]-wt;
end;
先把单位根的几个性质搞懂，然后就基本上可以理解这个分治了（最好是自己手算一下......我就懒得说什么了，自己都不是很理解，代码还是抄别人的）
const
s=;
type
cp=record
x,y:double;
end;
arr=array[.. shl ]of cp;
var
c:array[..]of int64;
a,b,w,tt:arr;
n,i,p:longint;
st:ansistring;
wt:cp; operator *(var a,b:cp)c:cp;
begin
c.x:=a.x*b.x-a.y*b.y;
c.y:=a.x*b.y+a.y*b.x;
end; operator +(var a,b:cp)c:cp;
begin
c.x:=a.x+b.x;
c.y:=a.y+b.y;
end; operator -(var a,b:cp)c:cp;
begin
c.x:=a.x-b.x;
c.y:=a.y-b.y;
end; procedure dft(var a:arr;s,t:longint);
begin
if n>>t= then exit;
dft(a,s,t+);
dft(a,s+<<t,t+);
for i:= to n>>(t+)- do
begin
p:=i<<(t+)+s;
wt:=w[i<<t]*a[p+<<t];
tt[i]:=a[p]+wt;
tt[i+n>>(t+)]:=a[p]-wt;
end;
for i:= to n>>t- do
a[i<<t+s]:=tt[i];
end; procedure get(var a:arr);
var
i,l,ll:longint;
c:char;
begin
read(c);
st:='';
while (ord(c)>=ord('')) and (ord(c)<=ord('')) do
begin
st:=st+c;
read(c);
end;
while length(st)mod s<> do
insert('',st,);
ll:=length(st)div s;
for l:= to ll do
val(copy(st,l*s-s+,s),a[ll-l].x);
while n>><l do
n:=n<<;
end; begin
n:=;
get(a);
get(b);
for i:= to n- do
w[i].x:=cos(pi**i/n);
for i:= to n- do
w[i].y:=sin(pi**i/n);
dft(a,,);
dft(b,,);
for i:= to n- do
a[i]:=a[i]*b[i];
for i:= to n- do
w[i].y:=-w[i].y;
dft(a,,);
for i:= to n- do
begin
c[i]:=c[i]+round(a[i].x/n);
c[i+]:=c[i] div ;
c[i]:=c[i] mod ;
end;
while (c[i]=) and (i>) do
dec(i);
for p:=i downto do
begin
str(c[p],st);
while (i<>p) and (length(st)<s) do
st:=''+st;
write(st);
end;
end.
又写了一遍233
const
maxn=;
type
cp=record
x,y:double;
end;
arr=array[..maxn]of cp;
var
a,b,w,tt:arr;
n:longint;
s:ansistring;
c:array[..maxn]of longint; operator -(a,b:cp)c:cp;
begin
c.x:=a.x-b.x;
c.y:=a.y-b.y;
end; operator +(a,b:cp)c:cp;
begin
c.x:=a.x+b.x;
c.y:=a.y+b.y;
end; operator *(a,b:cp)c:cp;
begin
c.x:=a.x*b.x-a.y*b.y;
c.y:=a.x*b.y+a.y*b.x;
end; procedure get(var a:arr);
var
c:char;
i,len:longint;
begin
s:='';
read(c);
while c in[''..''] do
begin
s:=s+c;
read(c);
end;
len:=length(s);
for i:= to len do
a[len-i].x:=ord(s[i])-ord('');
while n<len<< do
n:=n<<;
end; procedure dft(var a:arr;s,t:longint);
var
i,p:longint;
wt:cp;
begin
if n>>t= then exit;
dft(a,s+<<t,t+);dft(a,s,t+);
for i:= to n>>t>>- do
begin
p:=i<<t<<+s;
wt:=w[i<<t]*a[p+<<t];
tt[i]:=a[p]+wt;
tt[i+n>>t>>]:=a[p]-wt;
end;
for i:= to n>>t- do
a[s+i<<t]:=tt[i];
end; procedure main;
var
i:longint;
begin
n:=;get(a);get(b);
for i:= to n- do w[i].x:=cos(pi**i/n);
for i:= to n- do w[i].y:=sin(pi**i/n);
dft(a,,);dft(b,,);
for i:= to n- do a[i]:=a[i]*b[i];
for i:= to n- do w[i].y:=-w[i].y;
dft(a,,);
for i:= to n- do c[i]:=round(a[i].x/n);
for i:= to n- do
begin
inc(c[i+],c[i]div );
c[i]:=c[i]mod ;
end;
i:=n-;
while (c[i]=) and (i>) do dec(i);
for i:=i downto do write(c[i]);
end; begin
main;
end.