Question

高精度乘法

10000位为什么超时
代码如下
type
pt=array[0..10000] of longint;
var
s:ansistring;
la,lb,lc:longint;
a,b,c:pt;

procedure init;
var i:longint;
begin
readln(s);
la:=length(s);
for i:=1 to la do
a[la-i+1]:=ord(s[i])-ord('0');
readln(s);
lb:=length(s);
for i:=1 to lb do
b[lb-i+1]:=ord(s[i])-ord('0');
end;

procedure mult(a,b:pt);
var i,j,x:longint;
begin
for i:=1 to la do
begin
x:=0;
for j:=1 to lb do
begin
x:=a[i]*b[j]+x div 10+c[i+j-1];

c[i+j-1]:=x mod 10;
end;
c[i+lb]:=x div 10;
end;
lc:=la+lb;
while (c[lc]=0) and (lc>1) do dec(lc);

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

begin
init;
mult(a,b);
end.

Answer 1

program gaojingdu;
var
a,b,c:array[0..20000] of 0..9;
n:string;
i,j,x:integer;
begin
readln(n);
a[0]:=length(n);
for i:=1 to a[0] do a[a[0]-i+1]:=ord(n[i])-ord('0');
readln(n);
b[0]:=length(n);
for i:=1 to b[0] do b[b[0]-i+1]:=ord(n[i])-ord('0');for i:=1 to a[0] do
begin
x:=0;
for j:=1 to b[0] do
begin
x := a[i]*b[j]+ x div 10 +c[i+j-1];
c[i+j-1]:=x mod 10;

end;
c[i+j]:= x div 10;
end;
c[0]:=i+j;
while (c[c[0]]=0) and (c[0]>1) do c[0]:=c[0]-1;
for i:=c[0] downto 1 do write(c[i]);
readln;
end.

我这个应该可以。。

再看你的。
首先数组不够大，至少开到20000。

再者，n2 的时间复杂度，至少100000000次计算，再乘上每次3~4步，计算机没那么快诶。

Answer 2

数组开小了吧。。。
2个万位数相乘，结果的长度至少为l1+l2-1,数组仅开1万似乎不够
而且数位太大超时也很正常

Answer 3

我们还没学过呢