#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
void convert1(char s[],int a[])
{
int i,j=1,k=1,n=strlen(s);
for(i=1;i<=n;i++)
{
if(k==10000)
{
j++;
k=1;
}
a[j]=a[j]+(s[n-i]-'0')*k;
k=k*10;
}
a[0]=j;
}
void add1(int a[],int b[],int c[])
{
int i,n=a[0]>b[0]?a[0]:b[0];
for(i=1;i<=n;i++)
{
c[i]+=(a[i]+b[i]);
c[i+1]+=c[i]/10000;
c[i]%=10000;
}
n=n+1;
while(c[n]==0&&n>1)n--;
c[0]=n;
}
void mult1(int a[],int b[],int c[])
{
int i,j,n;
for(i=1;i<=a[0];i++)
{
for(j=1;j<=b[0];j++)
{
c[i+j-1]+=a[i]*b[j];
c[i+j]+=c[i+j-1]/10000;
c[i+j-1]%=10000;
}
}
n=a[0]+b[0]+1;
while(c[n]==0&&n>1)n--;
c[0]=n;
}

int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
char s[100000];
int a[100000]={0};
int b[100000]={0};
int c[100000]={0};
int i;
cin>>s;
convert1(s,a);
cin>>s;
convert1(s,b);
mult1(a,b,c);
printf("%d",c[c[0]]);
for(i=c[0]-1;i>=1;i--)
printf("%04d",c[i]);
return 0;
}

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
void convert(char s[],int a[])
{
int i,n=strlen(s);
for(i=1;i<=n;i++)
{
a[i]=s[n-i]-'0';

}
a[0]=n;
}
void mult(int a[],int b[],int c[])
{
int i,j,n;
for(i=1;i<=a[0];i++)
{
for(j=1;j<=b[0];j++)
{
c[i+j-1]=c[i+j-1]+a[i]*b[j];
c[i+j]=c[i+j]+c[i+j-1]/10;
c[i+j-1]=c[i+j-1]%10;
}
}
n=a[0]+b[0]+1;
while(c[n]==0&&n>1)
n--;
c[0]=n;
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
char s[100000];
int a[100000]={0};
int b[100000]={0};
int c[100000]={0};
int i;
cin>>s;
convert(s,a);
cin>>s;
convert(s,b);
mult(a,b,c);
for(i=c[0];i>=1;i--)
cout<<c[i];
return 0;
}

大整数乘法的优化策略：1.压位，高进制。2.预存数法
以a*b为例,把a*0、a*1、a*2,a*3.....求出10个来存在数组里面，然后直接移位相加，避免了多次乘法，将加法代替了乘法。
#include<iostream>
#include<string.h>
using namespace std;
#define size 10005
int a[size], b[size];
int ans[size<<1];
void toNum(char s[], int n[]){
memset(n, 0, sizeof(n));
int i = 0;
while (s[i])i++;
int j;
for (j = 0; j < i; j++){
n[j] = s[i - 1 - j] - '0';
}
}
int main(){
freopen("in.txt", "r", stdin);
char sa[size], sb[size];
cin >> sa >> sb;
toNum(sa, a);
toNum(sb, b);
memset(ans, 0, sizeof(ans));

int i,j;
for (i = 0; i < size; i++){
for (j = 0; j < size; j++){
ans[i + j] += a[i] * b[j];
}
}
for (i = 0; i < (size<<1); i++){
ans[i + 1] += ans[i] / 10;
ans[i] %= 10;
}
for (i = (size<<1)-1; ans[i] == 0; i--);
for (; i >= 0; i--)cout << ans[i];
return 0;
}

python为啥如此强悍？快到正无穷。
a=raw_input()
b=raw_input()
print int(a)*int(b)

我彻底明白了换语言的重要性。
用Pascal压四位，但怎么调都只有25分……
Copy了一下Python 2.x的程序，三行，AC……
模板太有用了！！！

####Python 2.x程序
a=raw_input()
b=raw_input()
print int(a)*int(b)

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
char st1[10005],st2[10005];
int a[10005],b[10005],c[20005];
int i,j,len1,len2;

cin >> st1 >> st2;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));

len1=strlen(st1);
j=1;
for (i=len1-1;i>=0;i--)
{
a[j++]=st1[i]-'0';
}

len2=strlen(st2);
j=1;
for (i=len2-1;i>=0;i--)
{
b[j++]=st2[i]-'0';
}

for (i=1;i<=len1;i++)
for (j=1;j<=len2;j++)
c[i+j-1]+=a[i]*b[j];

for (i=1;i<len1+len2;i++)
{
c[i+1]+=c[i]/10;
c[i]%=10;
}

while (!c[i] && i>1) i--;
while (i)
printf("%d",c[i--]);
printf("\n");
return 0;
}

只要会压4位，处理好0000的情况，基本AC

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int tenpower[4]={1,10,100,1000};

class Bigint
{
private:
int len,data[15000];
public:
Bigint()
{
memset(data,0,sizeof(data));
len=0;
}
Bigint(char *str)
{
Bigint();
int length=strlen(str);
for(int i=0;i<=length;i++)
data[(length-i-1)>>2]+=(str[i]-48)*tenpower[(length-i-1)&3];
len=(length&3)?(length>>2):(length>>2)-1;
}
Bigint operator * (const Bigint b)const
{
Bigint ans;
for(int i=0;i<=len;i++)
for(int j=0;j<=b.len;j++)
{
ans.data[i+j]+=data[i]*b.data[j];
ans.data[i+j+1]+=ans.data[i+j]/10000;
ans.data[i+j]%=10000;
}
ans.len=len+b.len;
while (ans.data[ans.len+1]) ans.len++;
return ans;
}
void write()
{
printf("%d",data[len]);
for(int i=len-1;i>=0;i--)
printf("%04d",data[i]);
}
};

int main()
{
char str[10001];
Bigint a(gets(str)),b(gets(str)),ans=a*b;
ans.write();
return 0;
}

压4位终于过了！

block code

program ex;
var a,b,c:array[0..1000000] of longint;
la,lb,lc,num,i,j,w,lena,lenb:longint;
a1,a2:ansistring;
d:ansistring;
label ans;

begin
w:=1;
lena:=0;
lenb:=0;
fillchar(c,sizeof(c),0);

readln(a1);
readln(a2);
if (a1='0') or (a2='0') then
begin
write('0');
exit;
end;

la:=length(a1);
lb:=length(a2);

for i:=la downto 1 do
if (i-1) mod 4=0 then
begin
val(copy(a1,la-4*w+1,4),a[w]);
delete(a1,la-4*w+1,4);
w:=w+1;
lena:=lena+1;
end;

w:=1;
for i:=lb downto 1 do
if (i-1) mod 4=0 then
begin
val(copy(a2,lb-4*w+1,4),b[w]);
delete(a2,lb-4*w+1,4);
w:=w+1;
lenb:=lenb+1;
end;

for i:=1 to la do
for j:=1 to lb do
begin
c[i+j-1]:=a[i]*b[j]+c[i+j-1];
num:=0;
if c[i+j-1]>=10000 then
begin
num:=c[i+j-1] div 10000;
c[i+j-1]:=c[i+j-1] mod 10000;
c[i+j]:=num+c[i+j];
end;
end;

lc:=lena+lenb;
while(c[lc]=0) and (lc>1) do dec(lc);

for i:=lc downto 1 do
begin
if (c[i]>=1000) or (i=lc) then
begin
write(c[i]);
goto ans;
end;

if c[i]=0 then
write('0000');

if (c[i]>0) and (c[i]<10) then
write('000',c[i]);

if (c[i]>=10) and (c[i]<100) then
write('00',c[i]);

if (c[i]>=100) and (c[i]<1000) then
write('0',c[i]);

ans:
end;

end.

压四位
program pro;
type mine=array[0..1000000]of longint;
var
s1,s2:ansistring;
n1,n2:mine;
i,j:longint;

procedure insert(st:ansistring; var x:mine);
var
len:longint;
begin
len:=length(st);
while len>=4 do
begin
inc(x[0]);
val(copy(st,len-3,4),x[x[0]]);
dec(len,4);
end;

if len>0 then
begin
inc(x[0]);
val(copy(st,1,len),x[x[0]]);
end;
end;

procedure mul(var a:mine; b:mine);
var
ii,jj:longint;
c:mine;
begin
fillchar(c,sizeof(c),0);
c[0]:=a[0]+b[0]-1;
for ii:=1 to a[0] do
for jj:=1 to b[0] do
begin
c[ii+jj]:=c[ii+jj]+(c[ii+jj-1]+a[ii]*b[jj])div 10000;
c[ii+jj-1]:=(c[ii+jj-1]+a[ii]*b[jj])mod 10000;
end;
while c[c[0]+1]>0 do inc(c[0]);
a:=c;
end;

procedure print(a:mine);
var
ii:longint;
begin
write(a[a[0]]);
for ii:=a[0]-1 downto 1 do
begin
if a[ii]<1000 then write(0);
if a[ii]<100 then write(0);
if a[ii]<10 then write(0);
write(a[ii]);
end;
end;

begin

readln(s1);
readln(s2);
insert(s1,n1);
insert(s2,n2);
mul(n1,n2);
print(n1);

end.

s=int(raw_input())
b=int(raw_input())
print s*b
python

用模版一次过。。

string che(string a,string b)
{
int a1[maxx+10]={0},a2[maxx+10]={0},cheng[2*maxx+10]={0};
int i,len1=a.length(),len2=b.length(),j=0;
for(i=len1-1;i>=0;i--)
a1[j++]=a[i]-48;
j=0;
for(i=len2-1;i>=0;i--)
a2[j++]=b[i]-48;
for(i=0;i<len2;i++)
for(j=0;j<len1;j++)
cheng[i+j]+=a2[i]*a1[j];
for(i=0;i<=maxx*2;i++)
if(cheng[i]>=10)
{
cheng[i+1]+=cheng[i]/10;
cheng[i]%=10;
}
int t=2*maxx+9;
while(cheng[t]==0&&t>0) t--;
char d[2*maxx+10];
for(i=0;i<=t;i++)
d[i]=cheng[t-i]+48;
d[i]='\0';
string c=d;
return c;
}

一个数组4个数 不超过100ms
var

a,b,c:array[0..20001]of longint;

n1,n2:ansistring;

lena,lenb,lenc,i,j,jin,k,x,y,l:longint;

begin

readln(n1);

readln(n2);

x:=length(n1) mod 4;

if x<>0 then for i:=1 to 4-x do n1:='0'+n1;

y:=length(n2) mod 4;

if y<>0 then for i:=1 to 4-y do n2:='0'+n2;

lena:=length(n1) div 4 ;

lenb:=length(n2) div 4 ;

l:=1;

for i:=1 to length(n1) do

begin

k:=i mod 4;

if k=1 then inc(j);

a[j]:=(ord(n1[4*lena-i+1])-ord('0'))*l+a[j];

l:=10*l;

if l=10000 then l:=1;

end;

l:=1;

j:=0;

for i:=1 to length(n2) do

begin

k:=i mod 4;

if k=1 then inc(j);

b[j]:=(ord(n2[4*lenb-i+1])-ord('0'))*l+b[j];

l:=10*l;

if l=10000 then l:=1;

end;

for i:=1 to lena do

begin

for j:=1 to lenb do

begin

c[i+j-1]:=a[i]*b[j]+c[i+j-1]+jin;

jin:=c[i+j-1] div 10000 ;

c[i+j-1]:=c[i+j-1] mod 10000;

end;

c[i+j]:=jin;

jin:=0;

end;

lenc:=lena+lenb;

while (c[lenc]=0) and(lenc>0) do dec(lenc);

if lenc=0 then write(0)

else

begin

write(c[lenc]);

for i:=lenc-1 downto 1 do begin

x:=trunc(ln(c[i])/ln(10))+1;

for j:=1 to 4-x do write(0);

write(c[i]);

end;

end;

end.

#include <stdio.h>
#include <string.h>
#define maxn 10050
char ch1[maxn];
char ch2[maxn];
int a[maxn]={0};
int b[maxn]={0};
int c[maxn+maxn]={0};
int main()
{
scanf("%s%s",ch1,ch2);
int i,j,x=0,y=0;
int k1=strlen(ch1);
int k2=strlen(ch2);
for(i=1;i<=k1;i+=4)
{
a[++x]=ch1[k1-i]-'0';
if( i+1<=k1 ) a[x]+=( ch1[k1-i-1]-'0' )*10;
if( i+2<=k1 ) a[x]+=( ch1[k1-i-2]-'0' )*100;
if( i+3<=k1 ) a[x]+=( ch1[k1-i-3]-'0' )*1000;
}
for(i=1;i<=k2;i+=4)
{
b[++y]=ch2[k2-i]-'0';
if( i+1<=k2 ) b[y]+=( ch2[k2-i-1]-'0' )*10;
if( i+2<=k2 ) b[y]+=( ch2[k2-i-2]-'0' )*100;
if( i+3<=k2 ) b[y]+=( ch2[k2-i-3]-'0' )*1000;
}
for(i=1;i<=x;i++)
for(j=1;j<=y;j++)
{
c[i+j-1]+=a[i]*b[j];
c[i+j]+=c[i+j-1]/10000;
c[i+j-1]%=10000;
}
for(i=x+y;i>=1;i--)
if( c[i] ) break;
for(j=i;j>=1;j--)
{
if( i==j )
printf("%d",c[j]);
else
printf("%04d",c[j]);
}
putchar(10);
return 0;
}

Python：
a=raw_input()
b=raw_input()
print int(a)*int(b)

#include<iostream>
#include<algorithm>
using namespace std;
const int L=100005;
string mul(string a,string b)
{
string s;
int na[L],nb[L],nc[2*L];
fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+2*L,0);
for(int i=a.size()-1,j=1;i>=0;i--,j++) na[j]=a[i]-'0';
for(int i=b.size()-1,j=1;i>=0;i--,j++) nb[j]=b[i]-'0';
for(int i=1;i<=a.size();i++)
for(int j=1;j<=b.size();j++)
nc[i+j-1]+=na[i]*nb[j];
for(int i=1;i<=a.size()+b.size();i++)
nc[i+1]+=nc[i]/10,nc[i]%=10;
if(nc[a.size()+b.size()]) s+=nc[a.size()+b.size()]+'0';
for(int i=a.size()+b.size()-1;i>=1;i--)
s+=nc[i]+'0';
return s;
}
int main()
{
string a,b;
while(cin>>a>>b)
{
cout<<mul(a,b)<<endl;
}
return 0;
}

我突然发现。。。用longint比integer快了400多ms
测试数据 #0: Accepted, time = 15 ms, mem = 1004 KiB, score = 25
测试数据 #1: Accepted, time = 15 ms, mem = 1008 KiB, score = 25
测试数据 #2: Accepted, time = 0 ms, mem = 1264 KiB, score = 25
测试数据 #3: Accepted, time = 671 ms, mem = 1264 KiB, score = 25
Accepted, time = 701 ms, mem = 1264 KiB, score = 100
测试数据 #0: Accepted, time = 0 ms, mem = 884 KiB, score = 25
测试数据 #1: Accepted, time = 0 ms, mem = 888 KiB, score = 25
测试数据 #2: Accepted, time = 31 ms, mem = 1148 KiB, score = 25
测试数据 #3: TimeLimitExceeded, time = 1015 ms, mem = 1148 KiB, score = 0
TimeLimitExceeded, time = 1046 ms, mem = 1148 KiB, score = 75

刚开始数组竟然只开到10000QwQ
贴代码：
var s1,s2:ansistring;
a,b,c:array[1..20000] of longint;
i,j,len1,len2,len3:longint;
begin
readln(s1);
readln(s2);
len1:=length(s1); len2:=length(s2);
for i:=len1 downto 1 do a[i]:=ord(s1[len1+1-i])-48;
for i:=len2 downto 1 do b[i]:=ord(s2[len2+1-i])-48;
for i:=1 to len1 do
for j:=1 to len2 do
c[i+j-1]:=c[i+j-1]+a[i]*b[j];
len3:=len1+len2-1;
for i:=1 to len3 do begin
inc(c[i+1],c[i] div 10);
c[i]:=c[i] mod 10;
end;
while c[len3+1]>0 do inc(len3);
for i:=len3 downto 1 do write(c[i]);
end.

//This program is made by WUYIFAN.
//Can not edit the program.
//Copyright 2014 WYF International(C) All rights reserved.
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char Str[10010];
long Alen,Blen,L,A[10010],B[10010],Ans[20020];
int main()
{
long a,b;
scanf("%s",&Str);
Alen=strlen(Str);
for(a=0;a<Alen;a++) A[a]=Str[Alen-1-a]-'0';
scanf("%s",&Str);
Blen=strlen(Str);
for(a=0;a<Blen;a++) B[a]=Str[Blen-1-a]-'0';
for(a=0;a<Alen;a++)
for(b=0;b<Blen;b++) Ans[a+b]+=A[a]*B[b];
L=Alen+Blen-2;a=0;b=0;
while(a<=L){
Ans[a]+=b;
b=Ans[a]/10;
Ans[a]%=10;
if(a==L&&b!=0) L++;
a++;
}
for(;L>=0;L--)
printf("%d\n",Ans[L]);
system("PAUSE");
return 0;
}

a=raw_input()
b=raw_input()
print int(a)*int(b)
秒杀。。。

include <iostream>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
char a[20001],b[20001];
int c[20001],d[20001],e[20001];
int main(){
cin>>a>>b;
int i,j,k=1,la=strlen(a),lb=strlen(b);
for(i=0;i<la;i++) d[la-i-1]=a[i]-48;
for(i=0;i<lb;i++) e[lb-i-1]=b[i]-48;
for(i=0;i<=19999;i++)
for(j=0;j<=19999;j++) c[i+j]+=d[i]*e[j];

for(i=0;i<=19999;i++)
if(c[i]>=10) c[i+1]+=c[i]/10,c[i]=c[i]%10;

for(i=19999;i>=0;i--)
{if(c[i]!=0) break;}
if(c[i]==0) {cout<<"0";k=0;}

for(j=i;j>=0;j--){
if(k==0) break;
cout<<c[j];
}
cout<<endl;
return 0;
}
#include <iostream>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
char a[20001],b[20001];
int c[20001],d[20001],e[20001];
int main(){
cin>>a>>b;
int i,j,k=1,la=strlen(a),lb=strlen(b);
for(i=0;i<la;i++) d[la-i-1]=a[i]-48;
for(i=0;i<lb;i++) e[lb-i-1]=b[i]-48;
for(i=0;i<=19999;i++)
for(j=0;j<=19999;j++) c[i+j]+=d[i]*e[j];

for(i=0;i<=19999;i++)
if(c[i]>=10) c[i+1]+=c[i]/10,c[i]=c[i]%10;

for(i=19999;i>=0;i--)
{if(c[i]!=0) break;}
if(c[i]==0) {cout<<"0";k=0;}

for(j=i;j>=0;j--){
if(k==0) break;
cout<<c[j];
}
cout<<endl;
return 0;
}
#include <iostream>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
char a[20001],b[20001];
int c[20001],d[20001],e[20001];
int main(){
cin>>a>>b;
int i,j,k=1,la=strlen(a),lb=strlen(b);
for(i=0;i<la;i++) d[la-i-1]=a[i]-48;
for(i=0;i<lb;i++) e[lb-i-1]=b[i]-48;
for(i=0;i<=19999;i++)
for(j=0;j<=19999;j++) c[i+j]+=d[i]*e[j];

for(i=0;i<=19999;i++)
if(c[i]>=10) c[i+1]+=c[i]/10,c[i]=c[i]%10;

for(i=19999;i>=0;i--)
{if(c[i]!=0) break;}
if(c[i]==0) {cout<<"0";k=0;}

for(j=i;j>=0;j--){
if(k==0) break;
cout<<c[j];
}
cout<<endl;
return 0;
}