题解 - Vijos

0

qiusheng320 LV 8 @ 2009-07-23 16:19:33

#include

#define M 10000

int al[M],bl[M],c[2*M];

char a[M],b[M];

int main()

{

int xa,xb,i,h,j;

scanf("%s",a);

scanf("%s",b);

for (xa = 0;a[xa] != '\0' && a[xa] != '\n';xa++);

for (xb = 0;b[xb] != '\0' && b[xb] !='\n';xb++);

for (i = 0;i < xa;i++) {

j = (xa - i - 1) / 4;

al[j] = al[j]* 10 + a[i] - '0';

}

xa = (xa + 3) / 4;

for (i = 0;i < xb;i++) {

j = (xb - i - 1) / 4;

bl[j] = bl[j] * 10 + b[i] - '0';

}

xb = (xb + 3) / 4;

for (i = 0;i < xb;i++) {

c[i] += al[0] * bl[i];

for (j = 1;j < xa;j++) {

c[j+i] += al[j] * bl[i];

c[j+i] += c[j+i-1] / 10000;

c[j+i-1] %= 10000;

}

}

xa =xa +xb-1;

while (c[xa-1] >= 10000) {

++xa;

c[xa-1] = c[xa-2] / 10000;

c[xa-2] %= 10000;

}

while (c[xa] == 0&&xa!=0) {

xa--;

}

printf("%d",c[xa]);

--xa;

while (xa >= 0) {

printf("%d%d%d%d",c[xa] /1000,(c[xa] /100) %10,(c[xa] /10) % 10,c[xa] % 10);

xa--;

}

return 0;

}

0

junfpc LV 8 @ 2009-07-27 15:14:00

编译通过...

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

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

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

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

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

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

var tmp1,tmp2,tmp3:ansistring;

a,b,c,max1,max2:longint;

a1,a2:array[1..10000] of integer;

a3:array[1..20000] of integer;

procedure huan(var a,b:integer);

var c:integer;

begin

c:=a;

a:=b;

b:=c;

end;

procedure cf;

var a,b,c,p:longint;

d:boolean;

begin

for a:=1 to max1 do

begin

c:=0;

for b:=1 to max2 do

begin

c:=a3[a+b-1]+c+a1[a]*a2[ b ];

a3[a+b-1]:=c mod 10000;

c:=c div 10000;

end;

p:=max2+a;

while c0 do

begin

a3[p]:=c mod 10000;

c:=c div 10000;

p:=p+1;

end;

end;

d:=false;

for a:=20000 downto 1 do

if (d)or(a3[a]0) then

begin

if d then

begin

if a3[a]

0

jiamomo LV 7 @ 2009-07-21 10:29:36

嘿嘿

万进制终于过了

哈哈哈我号佩服我自己

贴的是彩色代码！！！哈哈

#include#includechar a[10001]={"0"},b[10001]={"0"};int c[10012]={,};int main(){int lena=,lenb=;int i,j,k;int temp=;long t,r=;int la,lb;int d[4]={};gets(a);gets(b);lena=strlen(a);lenb=strlen(b);for(i=;i

0

wilsonlym LV 8 @ 2009-07-18 15:07:20

用万进制，秒杀

program gaocheng;

var

s1,s2:ansistring;

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

c:array[0..5505]of longint;

i,j:longint;

begin

readln(s1);

a[0]:=length(s1)div 4;

for i:=1 to a[0] do

val(copy(s1,length(s1)-4*i+1,4),a[i]);

if (length(s1)mod 4)>0 then

begin

inc(a[0]);

val(copy(s1,1,length(s1)mod 4),a[a[0]]);

end;

readln(s2);

b[0]:=length(s2)div 4;

for i:=1 to b[0] do

val(copy(s2,length(s2)-4*i+1,4),b[i]);

if (length(s2)mod 4)>0 then

begin

inc(b[0]);

val(copy(s2,1,length(s2)mod 4),b[b[0]]);

end;

for i:=1 to a[0] do

for j:=1 to b[0] do

begin

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

c:=c+cdiv 10000;

c:=cmod 10000;

end;

c[0]:=a[0]+b[0];

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

write(c[c[0]]);

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

begin

write(c[i]div 1000);

write((c[i]div 100)mod 10);

write((c[i]mod 100)div 10);

write(c[i]mod 10);

end;

writeln;

end.

0

我是姜逸伦大神 LV 8 @ 2009-07-17 16:46:06

水题

压8位 0MS闪过

0

chenrenfei LV 8 @ 2009-07-15 15:07:00

var

a,b:string;

x,y,z:array[1..1000] of integer;

f:array[1..1000,1..1000] of integer;

i,k,j,e,l,m,o,d,g:integer;

h:boolean;

begin

readln(a);

readln(b);

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

k:=length(a);

j:=length(b);

m:=k+j;

l:=0;

for i:=1 to k do

begin

val(a[i],y[m+i-k]);

end;

for o:=1 to j do

begin

val(b[o],z[m+o-j]);

end;

for d:=m downto k+1 do

begin

for e:=m downto j+1 do

f[d,e-l]:=y[d]*z[e];

l:=l+1;

end;

for d:=m downto 1 do

for e:=1 to m do

begin

x[d]:=f[e,d]+x[d]+g;

g:=x[d] div 10;

x[d]:=x[d] mod 10;

end;

h:=false;

for d:=1 to m do

if (h) or (x[d]0) then begin

h:=true;

write(x[d]);

end;

if (h=false) then write('0');

end.

0

cd LV 7 @ 2009-07-12 00:25:26

快速傅立叶变换，O(NlogN)

0

nblt LV 8 @ 2009-09-04 12:22:56

Program av;

Type arr = array[1..40001] Of longint;

Var a,b,c: arr;

la,lb,lc: word;

i,j,n: integer;

x: longint;

ch: char;

s:ansistring;

Begin

readln(s);

n:=length(s);

la := (n-1) Div 4+1;

For i:=1 To n Do

Begin

ch:=s[i];

a[(n-i) div 4 +1] := a[(n-i) div 4+1]*10+ord(ch)-ord('0');

End;

readln(s);

n:=length(s);

lb:=(n-1)div 4+1;

For i:=1 To n Do

Begin

ch:=s[i];

b[(n-i) div 4 +1] :=b[(n-i) div 4+1]*10+ ord(ch)-ord('0')

End;

For i:=1 To la Do

For j:=1 To lb Do

begin

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

inc(c,c div 10000);

c:=c mod 10000;

end;

if c[la+lb]0 Then lc := la+lb

Else lc := la+lb-1;

write(c[lc]);

For i:=lc-1 Downto 1 Do

Begin

if c[i] div 1000 =0 then write(0);

if c[i] div 100 =0 then write(0);

if c[i] div 10 =0 then write(0);

write(c[i]);

End;

End.

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

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

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

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

0

石力铭 LV 8 @ 2009-06-27 13:47:45

好

,

/ \

{ }

p !

; : ;

| : |

| : |

l ; l

l ; l

I ; I

I ; I

I ; I

I ; I

d | b

H | H

H | H

H I H

,;, H I H ,;,

;H@H; ;_H_;, ;H@H;

\Y/d\_,;|4H@HK|;,\_b\Y/' '\;MMMMM$@@@$MMMMM;/' "~~~\*;!8@8!;\*~~~" ;888; ;888; ;888; ;888; d8@8b O8@8O T808T \~`

贱……~~~~~~~~~~~~

0

d-rex LV 8 @ 2009-06-24 09:30:07

var

s1,s2:ansistring;

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

i,j,t1,t2,shu,k,y1,x,z,w,y:longint;

s:string;

begin

readln(s1);

k:=length(s1);

y1:=k;

t1:=0;

while k>=4 do

begin

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

val(s,shu);

inc(t1);

a[t1]:=shu;

dec(k,4);

end;

if y1 mod 40

then

begin

inc(t1);

s:=copy(s1,1,y1 mod 4);

val(s,shu);

a[t1]:=shu;

end;

readln(s2);

k:=length(s2);

y1:=k;

t2:=0;

while k>=4 do

begin

s:=copy(s2,k-3,4);

val(s,shu);

inc(t2);

b[t2]:=shu;

dec(k,4);

end;

if y1 mod 40

then

begin

inc(t2);

s:=copy(s2,1,y1 mod 4);

val(s,shu);

b[t2]:=shu;

end;

for i:=1 to t1 do

begin

for j:=1 to t2 do

begin

w:=i+j-1;

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

y:=x mod 10000;

z:=x div 10000;

c[w]:=c[w]+y;

c[w+1]:=c[w+1]+c[w] div 10000+z;

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

end;

end;

w:=t1+t2;

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

write(c[w]);

for i:=w-1 downto 1 do

begin

if (c[i]>=1000)then write(c[i]);

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

if (c[i]=10) then write('00',c[i]);

if (c[i]

0

luojiewei_tc LV 10 @ 2009-06-23 22:46:14

高精度能秒杀吗？？？？？？？？

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

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

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

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

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

我最后一个点为什么要 150ms

program LLL;

var

s1,s2:ansistring;

s:string;

l1,l2,ll1,ll2,i,j,l,k:longint;

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

begin

// assign(input,'input.txt');

// reset(input);

readln(s1);

readln(s2);

l1:=length(s1);

l2:=length(s2);

for i:=l1 downto 1 do

begin

s:=s1[i]+s;

if (l2-i+1) mod 4=0 then

begin

inc(ll1);

val(s,a[ll1]);

s:='';

end;

end;

if l1 mod 40 then

begin

inc(ll1);

val(s,a[ll1]);

end;

s:='';

for i:=l2 downto 1 do

begin

s:=s2[i]+s;

if (l2-i+1) mod 4=0 then

begin

inc(ll2);

val(s,b[ll2]);

s:='';

end;

end;

if l1 mod 40 then

begin

inc(ll2);

val(s,b[ll2]);

end;

for i:=1 to ll1 do

for j:=1 to ll2 do

begin

k:=i+j-1;

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

if c[k]>=10000 then

begin

inc(c[k+1],c[k] div 10000);

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

end;

end;

l:=ll1+ll2-1;

while c[l+1]>0 do

begin

inc(l);

c[l+1]:=c[l+1]+c[l] div 10000;

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

end;

write(c[l]);

for i:=l-1 downto 1 do

begin

if c[i]

0

GHL LV 10 @ 2009-06-21 10:59:17

我的程序

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

c:array[0..10000000] of longint;

n1,n2,n3:longint;

m:longint;

s:ansistring;

procedure cheng;

var i,j,x:longint;

begin

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

for i:=1 to n1 do

begin

x:=0;

for j:=1 to n2 do

begin

x:=a[i]*b[j]+x div 10+c;

c:=x mod 10;

end;

c:=x div 10;

end;

n3:=n1+n2;

while (c[n3]=0)and(n3>1) do

dec(n3);

for i:=n3 downto 1 do write(c[i]);

end;

begin

readln(s);

n1:=length(s);

for m:=1 to n1 do a[n1-m+1]:=ord(s[m])-48;

readln(s);

n2:=length(s);

for m:=1 to n2 do b[n2-m+1]:=ord(s[m])-48;

cheng;

end.

我觉得，加上过程更清晰！

0

wangpeng LV 9 @ 2009-06-17 21:25:38

编译通过...

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

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

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

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

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

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

my god 终于把它AC了！这么水的题交了这么多次！我撞豆腐死算了！

0

hhdllhflower LV 10 @ 2009-06-07 22:31:57

高精乘法、必需压位

var

s1,s2:ansistring;

t,len,len1,len2,i,j:longint;

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

begin

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

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

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

readln(s1);

readln(s2);

len1:=length(s1);

len2:=length(s2);

for i:=1 to len1 do

begin

j:=(len1-i) div 4+1;

a[j]:=a[j]*10+ord(s1[i])-48;

end;

for i:=1 to len2 do

begin

j:=(len2-i) div 4+1;

b[j]:=b[j]*10+ord(s2[i])-48;

end;

len1:=len1 div 4+1;

len2:=len2 div 4+1;

len:=len1+len2;

for i:=1 to len1 do

for j:=1 to len2 do

begin

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

c:=c+c div 10000;

c:=c mod 10000;

end;

while c[len]=0 do dec(len);

write(c[len]);

for i:=len-1 downto 1 do

begin

if (c[i]>=100) and (c[i]=10) and (c[i]

0

程序猎手 LV 7 @ 2009-06-06 10:31:33

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

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

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

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

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

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

水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！水！

0

xyk0058 LV 8 @ 2009-05-28 08:46:42

yhtrueno

压缩为10000进制的就可以了，但是数组要大一点......

0

yhtrueno LV 8 @ 2009-05-27 21:11:09

#include

using namespace std;

int main(){

long long int A[40001],B[40001],C[80010],x,y,z,s,m=1000000;

char a[40001],b[40001];

cin>>a>>b;

int sa=strlen(a),sb=strlen(b);

for(x=0;x=0;y--){

C[t]=C[t]+A[x]*B[y];

s=C[t]/10;

C[t]=C[t]%10;

C[--t]+=s;m=min(m,t);

}

}

while(C[m]==0)m++;

for(x=m;x

0

gnaggnoyil LV 10 @ 2009-05-25 08:45:11

operator *(a,b:num)c:num;

var i,j:longint;

begin

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

c[0]:=a[0]+b[0];

for i:=1 to a[0] do

for j:=1 to b[0] do

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

while c[c[0]]=0 do

dec(c[0]);

end;

一切解决.

0

Spirit_Night LV 10 @ 2009-05-23 12:49:26

忘了ansistring啊啊啊啊啊啊啊啊啊啊啊啊啊啊

0

ruizhao2 LV 8 @ 2009-05-10 23:59:14

考察：高精*高精 + 字符串处理 + 高精度算法的输出

注意：最后一组数据大概是20000位，而非不超过10000位。

题解

336 条题解

高精度乘法

信息

状态

开发

支持

题解

336 条题解

高精度乘法

信息

状态

开发

支持

还没有账户？

登录