文章目录
SuperGCD
问题描述:
Sheng bill有着惊人的心算能力,甚至能用大脑计算出两个巨大的数的GCD(最大公约数)!因此他经常和别人比赛计算GCD。有一天Sheng bill很嚣张地找到了你,并要求和你比赛,但是输给Sheng bill岂不是很丢脸!所以你决定写一个程序来教训他。
输入格式:
共两行:
第一行:一个数A。
第二行:一个数B。
输出格式:
一行,表示A和B的最大公约数。
样例输入:
12
54
样例输出:
6
数据范围:
对于20%的数据,0 < A,B ≤ 1018。
对于100%的数据,0 < A,B ≤ 1010000。
比较考察代码能力的题,高精度取模
program supergcd; const quick:int64=1000000000; type gj=array [0..1131] of int64; var a,b:int64; i,j,l:longint; k:int64; s1,s2:ansistring; n1,n2,temp:gj; function gcd (a,b:int64):int64; var i:int64; begin while a mod b <> 0 do begin i:=a mod b; a:=b; b:=i; end; exit(b); end; function convert (s:ansistring):gj; begin fillchar(temp,sizeof(temp),0); if length(s) mod 9 = 0 then k:=length(s) div 9 else k:=length(s) div 9 + 1; temp[0]:=k; l:=length(s); for i:=1 to l do begin j:=(l-i) div 9 + 1; temp[j]:=temp[j]*10+ord(s[i])-48; end; exit(temp); end; function over(var a:gj;s1,e1:longint;var b:gj;s2,e2:longint):boolean; begin if e1-s1<e2-s2 then exit(false); if e2-s2>e2-s2 then exit(true); for i:=e1-s1+1 downto 1 do if a[s1+i-1]<b[s2+i-1] then exit(false) else if a[s1+i-1]>b[s2+i-1] then exit(true); exit(true); end; function module (a,b:gj):gj; begin if not over(a,1,a[0],b,1,b[0]) then exit(a); for j:=a[0] downto b[0] do begin a[j]:=a[j]+a[j+1]*quick; a[j+1]:=0; if over(a,j-b[0]+1,j,b,1,b[0]) then begin k:=a[j] div (b[b[0]]+1); while k>0 do begin for i:=1 to b[0] do a[j-i+1]:=a[j-i+1]-k*b[b[0]-i+1]; for i:=b[0] downto 1 do if a[j-i+1]<0 then begin k:=-a[j-i+1] div quick; a[j-i+2]:=a[j-i+2]-k; a[j-i+1]:=a[j-i+1]+k*quick; if a[j-i+1]<0 then begin dec(a[j-i+2]); a[j-i+1]:=a[j-i+1]+quick; end; end; k:=a[j] div (b[b[0]]+1); end; while over(a,j-b[0]+1,j,b,1,b[0]) do begin for i:=b[0] downto 1 do begin a[j-i+1]:=a[j-i+1]-b[b[0]-i+1]; if a[j-i+1]<0 then begin dec(a[j-i+2]); a[j-i+1]:=a[j-i+1]+quick; end; end; end; end; end; while (a[0]>0)and(a[a[0]]=0) do dec(a[0]); if a[0]=0 then a[0]:=1; exit(a); end; begin assign(input,'gcd.in'); reset(input); assign(output,'gcd.out'); rewrite(output); readln(s1); readln(s2); if (length(s1)<=19)and(length(s2)<=19) then begin a:=0; for i:=1 to length(s1) do a:=a*10+ord(s1[i])-48; b:=0; for i:=1 to length(s2) do b:=b*10+ord(s2[i])-48; writeln(gcd(a,b)); end else begin n1:=convert(s1); n2:=convert(s2); while not ((n2[0]=1)and(n2[1]=0)) do begin temp:=module(n1,n2); n1:=n2; n2:=temp; end; write(n1[n1[0]]); for i:=n1[0]-1 downto 1 do begin j:=quick div 10; while j>0 do begin write(n1[i] div j mod 10); j:=j div 10; end; end; writeln; end; close(input); close(output); end.