#include <cstdlib>
#include <iostream>
#include <math.h>
#include <time.h>
#include <string.h>

using namespace std;

char a[100001];
char b[100001];
char c[200002];

int CheckInput(char *a,int &s1,int &z1,int &r1)
{

int i,m=strlen(a),e1,f=1;
s1=z1=0;
e1=-1;
for(i=0;i<m;i++)
{
if(a[i]=='0')
{
if(f) s1++;
z1++;
}
else
{
f=0;
e1=i;
}
a[i]-=48;
}
if(e1<0)
{
return 0;
}
r1=m-e1-1;
z1-=(m+s1-e1-1);
return e1-s1+1;
}

int MultiMultDo(char *a,int m,char *b,int n,int s,char *c)
{
int r=0,t,i,j,k,nPos=m+n+1;
memset(c,0,nPos+s);
if(s)
{
memset(c+nPos,'0',s);
}
nPos--;
for(i=n-1;i>=0;i--)
{
if(b[i])
{
k=nPos;
for(j=m-1;j>=0;j--)
{
t=c[k]+a[j]*b[i]+r;
c[k]=t%10;
r=t/10;
k--;
}
while(r)
{
t=c[k]+r;
c[k]=t%10;
r=t/10;
k--;
}
}
c[nPos]+='0';
nPos--;
}
k=-1;
for(i=0;i<=nPos;i++)
{
if(k<0 && c[i])
k=i;
c[i]+='0';
}
if(k<0)
k=nPos;
return k;
}

int MultiMult(char *a,char *b,char *c)
{
int i,s1=0,s2=0,z1=0,z2=0,m,n;
int r1,r2;
m=CheckInput(a,s1,z1,r1);
n=CheckInput(b,s2,z2,r2);
if(m*n==0)
{
*c++='0';
*c=0;
return 0;
}
if(z1>z2)
i=MultiMultDo(b+s2,n,a+s1,m,r1+r2,c);
else
i=MultiMultDo(a+s1,m,b+s2,n,r1+r2,c);
return i;
}

int main(int argc, char* argv[])
{
cin>>a>>b;
int n=MultiMult(a,b,c);
cout<<c+n<<endl;
system("PAUSE");
return 0;
}
#include <cstdlib>
#include <iostream>
#include <math.h>
#include <time.h>
#include <string.h>

using namespace std;

char a[100001];
char b[100001];
char c[200002];

int CheckInput(char *a,int &s1,int &z1,int &r1)
{

int i,m=strlen(a),e1,f=1;
s1=z1=0;
e1=-1;
for(i=0;i<m;i++)
{
if(a[i]=='0')
{
if(f) s1++;
z1++;
}
else
{
f=0;
e1=i;
}
a[i]-=48;
}
if(e1<0)
{
return 0;
}
r1=m-e1-1;
z1-=(m+s1-e1-1);
return e1-s1+1;
}

int MultiMultDo(char *a,int m,char *b,int n,int s,char *c)
{
int r=0,t,i,j,k,nPos=m+n+1;
memset(c,0,nPos+s);
if(s)
{
memset(c+nPos,'0',s);
}
nPos--;
for(i=n-1;i>=0;i--)
{
if(b[i])
{
k=nPos;
for(j=m-1;j>=0;j--)
{
t=c[k]+a[j]*b[i]+r;
c[k]=t%10;
r=t/10;
k--;
}
while(r)
{
t=c[k]+r;
c[k]=t%10;
r=t/10;
k--;
}
}
c[nPos]+='0';
nPos--;
}
k=-1;
for(i=0;i<=nPos;i++)
{
if(k<0 && c[i])
k=i;
c[i]+='0';
}
if(k<0)
k=nPos;
return k;
}

int MultiMult(char *a,char *b,char *c)
{
int i,s1=0,s2=0,z1=0,z2=0,m,n;
int r1,r2;
m=CheckInput(a,s1,z1,r1);
n=CheckInput(b,s2,z2,r2);
if(m*n==0)
{
*c++='0';
*c=0;
return 0;
}
if(z1>z2)
i=MultiMultDo(b+s2,n,a+s1,m,r1+r2,c);
else
i=MultiMultDo(a+s1,m,b+s2,n,r1+r2,c);
return i;
}

int main(int argc, char* argv[])
{
cin>>a>>b;
int n=MultiMult(a,b,c);
cout<<c+n<<endl;
system("PAUSE");
return 0;
}
#include <cstdlib>
#include <iostream>
#include <math.h>
#include <time.h>
#include <string.h>

using namespace std;

char a[100001];
char b[100001];
char c[200002];

int CheckInput(char *a,int &s1,int &z1,int &r1)
{

int i,m=strlen(a),e1,f=1;
s1=z1=0;
e1=-1;
for(i=0;i<m;i++)
{
if(a[i]=='0')
{
if(f) s1++;
z1++;
}
else
{
f=0;
e1=i;
}
a[i]-=48;
}
if(e1<0)
{
return 0;
}
r1=m-e1-1;
z1-=(m+s1-e1-1);
return e1-s1+1;
}

int MultiMultDo(char *a,int m,char *b,int n,int s,char *c)
{
int r=0,t,i,j,k,nPos=m+n+1;
memset(c,0,nPos+s);
if(s)
{
memset(c+nPos,'0',s);
}
nPos--;
for(i=n-1;i>=0;i--)
{
if(b[i])
{
k=nPos;
for(j=m-1;j>=0;j--)
{
t=c[k]+a[j]*b[i]+r;
c[k]=t%10;
r=t/10;
k--;
}
while(r)
{
t=c[k]+r;
c[k]=t%10;
r=t/10;
k--;
}
}
c[nPos]+='0';
nPos--;
}
k=-1;
for(i=0;i<=nPos;i++)
{
if(k<0 && c[i])
k=i;
c[i]+='0';
}
if(k<0)
k=nPos;
return k;
}

int MultiMult(char *a,char *b,char *c)
{
int i,s1=0,s2=0,z1=0,z2=0,m,n;
int r1,r2;
m=CheckInput(a,s1,z1,r1);
n=CheckInput(b,s2,z2,r2);
if(m*n==0)
{
*c++='0';
*c=0;
return 0;
}
if(z1>z2)
i=MultiMultDo(b+s2,n,a+s1,m,r1+r2,c);
else
i=MultiMultDo(a+s1,m,b+s2,n,r1+r2,c);
return i;
}

int main(int argc, char* argv[])
{
cin>>a>>b;
int n=MultiMult(a,b,c);
cout<<c+n<<endl;
system("PAUSE");
return 0;
}

#include <cstdlib>
#include <iostream>
#include <math.h>
#include <time.h>
#include <string.h>

using namespace std;

char a[100001];
char b[100001];
char c[200002];

int CheckInput(char *a,int &s1,int &z1,int &r1)
{

int i,m=strlen(a),e1,f=1;
s1=z1=0;
e1=-1;
//----------------------------------------------------
// a="000000123456999009888007020000000
// s1 e1 m

// r1=m-e1-1 z1=z1-(m+s1-e1-1)
///////////////////////////////////////////////////
for(i=0;i<m;i++)
{
if(a[i]=='0')
{
//统计0的个数和获得第一个非0的位置
if(f) s1++;
z1++;
}
else
{
//获得最后一个非0的位置
f=0;
e1=i;
}
a[i]-=48;
}
if(e1<0)
{
//全部为0, 数a=0
return 0;
}
//a最后连续0的数目
r1=m-e1-1;
//a中间0的个数
z1-=(m+s1-e1-1);
//a 的位数
return e1-s1+1;
}

int MultiMultDo(char *a,int m,char *b,int n,int s,char *c)
{
int r=0,t,i,j,k,nPos=m+n+1;
//m*n的结果最多m+n+1位
memset(c,0,nPos+s);
if(s)
{
//最后的s个0，先补上
memset(c+nPos,'0',s);
}
//开始的位置，c的个位数
nPos--;
for(i=n-1;i>=0;i--)
{
//乘数等0时不需要计算
if(b[i])
{
//当前的个位数
k=nPos;
//从后往前计算，避免了反转，如果前面已经反转了，也可以正序
for(j=m-1;j>=0;j--)
{
t=c[k]+a[j]*b[i]+r;
c[k]=t%10;
r=t/10;
k--;
}
//最高位可能需要一直进位
while(r)
{
t=c[k]+r;
c[k]=t%10;
r=t/10;
k--;
}
}
//将当前的个位设置成字符
c[nPos]+='0';
//下个乘数的个位前移1个
nPos--;
}
//将结果中前面到nPos位置转换为字符，找到第一个非0字符位置
//比如c="0000000334234324" k=7
k=-1;
for(i=0;i<=nPos;i++)
{
if(k<0 && c[i])
k=i;
c[i]+='0';
}
if(k<0)
k=nPos;
return k;
}

int MultiMult(char *a,char *b,char *c)
{
int i,s1=0,s2=0,z1=0,z2=0,m,n;
int r1,r2;
m=CheckInput(a,s1,z1,r1);
n=CheckInput(b,s2,z2,r2);
if(m*n==0)
{
//a或b=0
*c++='0';
*c=0;
return 0;
}
//为减少计算次数，总是用0多的那个数做乘数
if(z1>z2)
i=MultiMultDo(b+s2,n,a+s1,m,r1+r2,c);
else
i=MultiMultDo(a+s1,m,b+s2,n,r1+r2,c);
return i;
}

int main(int argc, char* argv[])
{
cin>>a>>b;
// scanf("%s",a);
// scanf("%s",b);
// memset(a,'9',10000);
// memset(b,'9',10000);
// unsigned int uTick=GetTickCount();
int n=MultiMult(a,b,c);
cout<<c+n<<endl;
system("PAUSE");
// uTick=GetTickCount()-uTick;
// printf("---%d---\n",uTick);
return 0;
}

Vijos题解：http://user.qzone.qq.com/616674147/2

Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步

Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步

a=raw-input()
c=raw-input()
print int(a)*int(b)

一用ansistring就过了。。。。。之前还不知道错在哪，交四次，错四次==

//发一个很快的算法

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#define N 400005
#define pi acos(-1.0) //PI值
using namespace std;

struct complex
{
double r,i;
complex(double real=0.0,double image=0.0)
{
r=real;
i=image;
}
//以下为三种虚数运算的定义
complex operator+(const complex o)
{
return complex(r+o.r,i+o.i);
}
complex operator-(const complex o)
{
return complex(r-o.r,i-o.i);
}
complex operator*(const complex o)
{
return complex(r*o.r-i*o.i,r*o.i+i*o.r);
}
}x1[N],x2[N];
char a[N/2],b[N/2];
int sum[N]; //结果存在sum里

void brc(complex *y,int l) //二进制平摊反转置换 O(logn)
{
register int i,j,k;
for(i=1,j=l/2;i<l-1;i++)
{
if(i<j) swap(y [i] ,y [j] ); //交换互为下标反转的元素
//i<j保证只交换一次
k=l/2;
while(j>=k) //由最高位检索，遇1变0，遇0变1，跳出
{
j-=k;
k/=2;
}
if(j<k) j+=k;
}
}

void fft(complex *y,int l,double on) //FFT O(nlogn)
//其中on==1时为DFT，on==-1为IDFT
{
register int h,i,j,k;
complex u,t;
brc(y,l); //调用反转置换
for(h=2;h<=l;h<<=1) //控制层数
{
//初始化单位复根
complex wn(cos(on*2*pi/h),sin(on*2*pi/h));
for(j=0;j<l;j+=h) //控制起始下标
{
complex w(1,0); //初始化螺旋因子
for(k=j;k<j+h/2;k++) //配对
{
u=y [k] ;
t=w*y[k+h/2];
y [k] =u+t;
y[k+h/2]=u-t;
w=w*wn; //更新螺旋因子
} //上面的操作叫蝴蝶操作
}
}
if(on==-1)
for(i=0;i<l;i++)
y [i] .r/=l; //IDFT
}

int main()
{
int l1,l2,l;
register int i;
while(~scanf("%s%s",a,b))
{
l1=strlen(a);
l2=strlen(b);
l=1;
while(l<l1*2 || l<l2*2) l<<=1; //将次数界变成2^n
//配合二分与反转置换
for(i=0;i<l1;i++) //倒置存入
{
x1 [i] .r=a[l1-i-1]-'0';
x1 [i] .i=0.0;
}
for(;i<l;i++)
x1 [i] .r=x1 [i] .i=0.0;
//将多余次数界初始化为0
for(i=0;i<l2;i++)
{
x2 [i] .r=b[l2-i-1]-'0';
x2 [i] .i=0.0;
}
for(;i<l;i++)
x2 [i] .r=x2 [i] .i=0.0;
fft(x1,l,1); //DFT(a)
fft(x2,l,1); //DFT(b)
for(i=0;i<l;i++)
x1 [i] =x1 [i] *x2 [i] ; //点乘结果存入a
fft(x1,l,-1); //IDFT(a*b)
for(i=0;i<l;i++)
sum [i] =x1 [i] .r+0.5; //四舍五入
for(i=0;i<l;i++) //进位
{
sum[i+1]+=sum [i] /10;
sum [i] %=10;
}
l=l1+l2-1;
while(sum [l] <=0 && l>0) l--; //检索最高位
for(i=l;i>=0;i--)
putchar(sum [i] +'0'); //倒序输出
printf("\n");
}
return 0;
}

var
a,b:array[1..1000] of integer;
c:array[1..2000] of integer; //c的长度可以计算出来吗？
la,lb,lc,x,i,j:integer;
s:ansistring;
begin
readln(s);la:=length(s);
for i:=1 to la do a[i]:=ord(s[la-i+1]) -ord('0');
readln(s);lb:=length(s);
for i:=1 to lb do b[i]:=ord(s[lb-i+1]) -ord('0');
for i:=1 to la do //一共要乘的次数
begin
x:=0;
for j:=1 to lb do //逐位相乘
begin
c[i+j-1]:=c[i+j-1]+a[i]*b[j]+x; //a的第i位和b的第j位相乘要放在c的i+j-1位，为什么？
x:=c[i+j-1] div 10; //要进位的数暂存在x中
c[i+j-1]:=c[i+j-1] mod 10;
end;
c[i+j]:=x;

end;
lc:=la+lb;
while (c[lc]=0) and (lc>1) do dec(lc); //去除前导0，用while不用if的原因是什么？
for i:=lc downto 1 do write(c[i]);
writeln;
end.
为啥错列

python:
a=int(raw_input())
b=int(raw_input())
print a*b

python秒杀

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

Java秒杀高精度，无压力

import java.util.Scanner;
import java.math.*;
public class Main
{
public static void main(String[] args)
{
Scanner cin=new Scanner(System.in);
BigInteger a,b;
a=cin.nextBigInteger();
b=cin.nextBigInteger();
System.out.println(a.multiply(b));
}
}

FFT.....
表示总用时58ms。。。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#define pi M_PI
using namespace std;
struct complex
{
double re, im;
complex() {}
complex(double re, double im) : re(re), im(im) {}
};
complex operator + (complex p1, complex p2) { return complex(p1.re + p2.re, p1.im + p2.im);}
complex operator - (complex p1, complex p2) { return complex(p1.re - p2.re, p1.im - p2.im);}
complex operator * (complex p1, complex p2) { return complex(p1.re * p2.re - p1.im * p2.im, p1.re * p2.im + p1.im * p2.re);}
complex x1[20001], x2[20001];
char s1[20001], s2[20001];
int len1, len2, len = 1;
int sum[80001];
void BRC(complex *p, int len)
{
for (int i = 1, j = (len >> 1); i < len - 1; i ++)
{
if (i < j) swap(p[i], p[j]);
int tmp = (len >> 1);
while (j >= tmp) j -= tmp, tmp >>= 1;
if (j < tmp) j += tmp;
}
}
void FFT(complex *p, int len, int flag)
{
complex tmp1, tmp2;
BRC(p, len);
for (int h = 2; h <= len; h <<= 1)
{
complex tp = complex(cos((flag * 1.0) * 2 * pi / (h * 1.0)), sin((flag * 1.0) * 2 * pi / (h * 1.0)));
for (int j = 0; j < len; j += h)
{
complex vp = complex(1.0, 0.0);
for (int k = j; k < j + (h >> 1); k ++)
tmp1 = p[k], tmp2 = vp * p[k + (h >> 1)], p[k] = tmp1 + tmp2, p[k + (h >> 1)] = tmp1 - tmp2, vp = vp * tp;
}
}
if (flag == -1)
for (int i = 0; i < len; i ++) p[i].re /= len;
}
int main( )
{
scanf("%s", s1); len1 = strlen(s1);
scanf("%s", s2); len2 = strlen(s2);
while (len < (len1 << 1) || len < (len2 << 1)) len <<= 1;
for (int i = 0; i < len1; i ++) x1[i] = complex((s1[len1 - 1 - i] - '0') * 1.0, 0.0);
for (int i = 0; i < len2; i ++) x2[i] = complex((s2[len2 - 1 - i] - '0') * 1.0, 0.0);
FFT(x1, len, 1), FFT(x2, len, 1);
for (int i = 0; i < len; i ++) x1[i] = x1[i] * x2[i];
FFT(x1, len, -1);
for (int i = 0; i < len; i ++) sum[i] = (int )(x1[i].re + 0.5);
for (int i = 0; i < len; i ++)
sum[i + 1] += sum[i] / 10, sum[i] %= 10;
len = len1 + len2 - 1;
while (sum[len] <= 0 && len > 0) -- len;
for (int i = len; i >= 0; i --)
printf("%d", sum[i]);
printf("\n");
return 0;
}

点击查看程序源码+详细题解

直接复制的程序，数组果断开小了。

话说tyvj的数据真心的水，一样的题目一样的数组呢边就ac了

~~~~~~~~~~~~~

const

n=10000;

var

x,y,z:array[0..20100]of integer;

s1,s2,s:string;

k1,k2,k,l1,l2,m,i,j,jw:integer;

t1,t2,t3:longint;

begin

readln(s1);readln(s2);

fillchar(x,sizeof(x),0);

fillchar(y,sizeof(y),0);

fillchar(z,sizeof(z),0);

l1:=length(s1);l2:=length(s2);

k1:=n;

repeat

s:=copy(s1,l1-3,4);

val(s,x[k1]);

dec(k1);

s1:=copy(s1,1,l1-4);

dec(l1,4);

until l1

之前数组开小了

~~

type arr=array[0..10000] of int64;

var a,b,c:arr;

procedure change(x:ansistring;var aa:arr);

var i:longint;s1:string[5];

begin

aa[0]:=length(x)div 4;

for i:=1 to aa[0] do

begin

s1:=copy(x,length(x)-3,4);

val(s1,aa[i]);

delete(x,length(x)-3,4);

end;

if x'' then

begin

inc(aa[0]);

val(x,aa[aa[0]]);

end;

end;

procedure print(x:arr);

var i:longint;

begin //writeln('af ',x[0],' ',x[1],' ',x[2]);

write(x[x[0]]);

for i:=x[0]-1 downto 1 do

begin

if x[i]>=1000 then

write(x[i]) else

if x[i]>=100 then

write('0',x[i]) else

if x[i]>=10 then

write('00',x[i])else

write('000',x[i]);

end;

writeln;

end;

procedure init;

var i,t,y:longint;s:ansistring;

begin

assign(input,'1.in');reset(input);

assign(output,'1.out');rewrite(output);

readln(s);

change(s,a);

readln(s);

change(s,b);

end;

procedure mutiply(a,b:arr;var c:arr);

var i,j:longint;

begin

for i:=1 to a[0] do

for j:=1 to b[0] do

begin

inc(c,a[i]*b[j]);

end;

c[0]:=a[0]+b[0]; // writeln(a[0]);

for i:=1 to c[0] do

begin

c:=c+c[i] div 10000;

c[i]:=c[i] mod 10000;

end;

if c[c[0]]=0 then dec(c[0]);

end;

procedure main;

begin

mutiply(a,b,c);

print(c);

end;

begin

init;

main;

end.

呜呜，数组开小了以为是500*4=20000，我的数学啊~~~Orz。。。

代码算是比较奇葩的面向对象，高精度BigNumber类，然后乘法四位压位秒杀。

#include

#include

#include

using namespace std;

class bign //BigNumber类，最大支持20000位 

{

private:

int num[5001]; //数值每四位分段储存 

int length; //数字的位数

public:

bign()

{

memset(this, 0, sizeof(bign));

}

bign& operator = (const bign* x) 

{

memcpy(this, x, sizeof(bign));

return *this;

}

bign& operator = (const char* x) //将倒序字符串赋值给bign对象 

{

length = strlen(x); //确定bign的位数 

int n = 0, //压位时的和 

r = 1, //压位时的权 

p = 5000; //指向num数组赋值的位置 

for (int i = 0; i < length; i++)

{

n += (x[i] - '0') * r;

r *= 10;

if ((i + 1) % 4 == 0) //每4位写入num数组，并清空压位临时变量 

{

num[p] = n;

n = 0;

r = 1;

p--;

}

}

if (n) //将最后残余的不足4位的数据写入 

num[p] = n;

return *this;

}

void output()

{

int head = 5000 - (length - 1) / 4; //找到num的起始位置 

printf("%d", num[head++]);

while (head < 5001)

printf("%04d", num[head++]);

}

bign operator * (const bign& x)

{

bign c;

int th = 5000 - (length - 1) / 4, //th = this_head，this的num起始位置 

xh = 5000 - (x.length - 1) / 4; //xh = x_head，x的num起始位置 

for (int it = 5000; it >= th; it--)

for (int ix = 5000; ix >= xh; ix--)

{

int p = it + ix - 5000,

temp = c.num[p] + num[it] * x.num[ix];

while (temp > 10000)

{

c.num[p] = temp % 10000;

p--;

temp = temp / 10000 + c.num[p];

}

c.num[p] = temp;

}

int maxcl = length + x.length; //c的length的最大可能值 

while (c.num[5000 - (maxcl - 1) / 4] == 0) //逐个判断，得到c的真实length 

maxcl--;

if (maxcl < 1) //当乘积为0时会出现maxcl = -1，校正这个BUG 

maxcl = 1;

c.length = maxcl;

return c;

}

};

int main()

{

bign a, b;

char sa[10001], sb[10001];

gets(sa); strrev(sa); //读入数字并反转，方便输入bign对象 

gets(sb); strrev(sb); 

a = sa;

b = sb;

bign c;

c = a * b;

c.output();

printf("\n");

return 0;

}

算法：高精度

注意不要弄成高位往低位乘了。。。

string要换

program p1040;

var

l1,l2,l3,i,j,k,l:longint;

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

s1,s2:ansistring;

begin

　　readln(s1);readln(s2);

　　l1:=length(s1);l2:=length(s2);

　　for i:=0 to l1-1 do

　　a[i]:=ord(s1[l1-i])-ord('0');

　　for i:=0 to l2-1 do b[i]:=ord(s2[l2-i])-ord('0');

　　for i:=l1-1 downto 0 do

　　 begin

　　　　for j:=l2-1 downto 1 do

　　　　 a:=a+a[i]*b[j];

　　　　a[i]:=a[i]*b[0];

　　 end;

　　k:=l1+l2-1;

　　for i:=0 to k-1 do

　　 begin

　　 a:=a[i] div 10 +a;

　　 a[i]:=a[i] mod 10;

　　 end;

if a[k]>0 then k:=k+1;

for i:=k-1 downto 0 do write(a[i]);

end.