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.

一次ac

新手过的第一道难度三的题！good！

规规矩矩的做法，没有压位，没有那么复杂，10进制普通做法就行

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.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 431ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：431ms

var

s1,s2:ANSIstring;

a,b:array[1..10000]of longint;

c:array[1..1000000]of longint;

i,j:longint;

begin

readln(s1);

readln(s2);

fillchar(a,sizeof(a),0);

fillchar(b,sizeof(b),0);

fillchar(c,sizeof(c),0);

for i:=1 to length(s1)do

a[length(s1)-i+1]:=ord(s1[i])-48;

for i:=1 to length(s2)do

b[length(s2)-i+1]:=ord(s2[i])-48;

for i:=1 to length(s1)do begin

for j:=1 to length(s2)do begin

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

end;

end;

j:=0;

repeat

inc(j);

if c[j]>=10

then begin

c[j+1]:=c[j+1]+c[j] div 10;

c[j]:=c[j] mod 10;

end;

until c[j+1]=0;

for i:=j downto 1 do

write(c[i]);

writeln;

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：75 有效耗时：0ms

随能帮我看看为什么超时

或怎样才不超时！

program p1040_1;

type arr=record

s:array[0..5000]of int64;

len:longint;

end;

var

x,i,j,l:longint;

str:ansistring;

a,b:arr;

function mul(a,b:arr):arr;

var

c:arr;

i,j:longint;

begin

fillchar(c,sizeof(c),0);

for i:=1 to a.len do

for j:=1 to b.len do

begin

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

inc(c.s,c.s div 100000000);

c.s:=c.s mod 100000000;

end;

c.len:=a.len+b.len+1;

while (c.s[c.len]=0)and(c.len>1) do dec(c.len);

mul:=c;

end;

begin

readln(str);

l:=length(str);

a.len:=l div 8;

for i:=1 to a.len do

val(copy(str,l-i*8+1,8),a.s[i]);

if l mod 80 then begin inc(a.len);val(copy(str,1,l mod 8),a.s[a.len]); end;

readln(str);

l:=length(str);

b.len:=l div 8;

for i:=1 to b.len do

val(copy(str,l-i*8+1,8),b.s[i]);

if l mod 80 then begin inc(b.len);val(copy(str,1,l mod 8),b.s); end;

a:=mul(a,b);

write(a.s[a.len]);

for i:=a.len-1 downto 1 do

begin

x:=10000000;

if a.s[i]=0 then

for j:=1 to 8 do

write(0);

while a.s[i]0 do

begin

if a.s[i] div x=0 then begin write(0);x:=x div 10; end

else begin write(a.s[i]);a.s[i]:=0 end;

end;

end;

end.

压了8位了 为什么还是没有秒杀 哎