黄金雅蠛蝶 黄金雅蠛蝶
Dies
关注数: 48 粉丝数: 228 发帖数: 11,401 关注贴吧数: 33
高精度阶乘求优化 认真写的高精度阶乘,但是比直接相乘快不了多少 希望大师们能指点优化: program gjd_fact_n; const    cade=10000000;    maxl=5200; type    gjd=array [0..maxl] of qword; var    nums:longint;    isp:array[1..40000] of boolean;    i,j,m,fa:longword;    t,r,temp:gjd; procedure init(var r:gjd); begin    fillchar(r,sizeof(r),0);    r[0]:=1;r[1]:=1; end; procedure square(var x:gjd); var    i,j:longint; begin    fillchar(temp,sizeof(temp),0);    temp[0]:=x[0]+x[0]-1;    for i:=1 to x[0] do      for j:=1 to x[0] do        inc(temp[i+j-1],x[i]*x[j]);    for i:=1 to temp[0] do    begin      inc(temp[i+1],temp[i] div cade);      temp[i]:=temp[i] mod cade;    end;    if temp[temp[0]+1]>0 then inc(temp[0]);    x:=temp; end; procedure times(var x,u:gjd); var    i,j:longint; begin    fillchar(temp,sizeof(temp),0);    temp[0]:=x[0]+u[0]-1;    for i:=1 to x[0] do      for j:=1 to u[0] do        inc(temp[i+j-1],x[i]*u[j]);    for i:=1 to temp[0] do    begin      inc(temp[i+1],temp[i] div cade);      temp[i]:=temp[i] mod cade;    end;    if temp[temp[0]+1]>0 then inc(temp[0]);    x:=temp; end; procedure times(var x:gjd;k:longword); var    i:longint; begin    for i:=1 to x[0] do       x[i]:=x[i]*k;    for i:=1 to x[0] do      begin        inc(x[i+1],x[i] div cade);        x[i]:=x[i] mod cade;      end;    if x[x[0]+1]>0 then inc(x[0]); end; procedure ksm(var x:gjd;u:qword;m:longword); var    digit:array[1..32] of boolean;    mx:longword=0;    i:longword; begin    fillchar(digit,sizeof(digit),0);    while m<>0 do    begin      inc(mx);      digit[mx]:=odd(m);      m:=m shr 1;    end;    for i:=mx downto 1 do    begin      square(x);      if digit[i] then times(x,u);    end; end; procedure opt(var x:gjd); var    i,j:longint;    s:string[7]; begin    write(x[x[0]]);    for i:=x[0]-1 downto 1 do    begin      str(x[i],s);      for j:=1 to 7-length(s) do write('0');      write(s);    end;    writeln; end; begin    readln(fa);    fillchar(isp,sizeof(isp),true);    isp[1]:=false;    for i:=2 to trunc(sqrt(fa)) do      if isp[i] then        for j:=2 to fa div i do isp[i*j]:=false;    init(r);    //for i:=2 to fa do    for i:=2 to fa shr 1 do      if isp[i] then      begin        m:=fa;        nums:=0;        while m>0 do        begin          m:=m div i;          inc(nums,m);        end;        init(t);        ksm(t,i,nums);        times(r,t);      end;    for i:=fa shr 1+1 to fa do      if isp[i] then        times(r,i);    //opt(r); end. 有一个问题,把 maxl 改成 16000 或 24000 后,程序明显会变慢(同样计算 10000!)。请问有没有好的解决方法?
首页 2 3 4 5 6 7 下一页