首先我们知道，对于两个数a,b，他们的gcd情况有如下形式的讨论
当a为奇数，b为偶数的时候gcd(a,b)=gcd(a div 2,b)
当b为奇数，a为偶数的时候gcd(a,b)=gcd(a,b div 2)
当a为偶数，b为偶数的时候gcd(a,b)=2*gcd(a div 2,b div 2)
当a为奇数，b为奇数的时候，根据欧几里德定律，有gcd(a,b)=gcd(a-b,b) (a>b)时
那么这道题就变成了不断地缩小a,b的范围了。直接高精就行了。当然数据为1,10^1000的时候会tle，题目比较良心没有这样的数据。
高精写渣了。
/************************************************************** Problem: 1876 User: BLADEVIL Language: Pascal Result: Time_Limit_Exceed****************************************************************/ //By BLADEVILvar s1, s2 :ansistring; f1, f2 :boolean; ans :ansistring; a, b, c :array[0..100000] of longint; i :longint; doit :longint; function max(s1,s2:ansistring):boolean;begin if length(s1)>length(s2) then exit(true); if (length(s1)=length(s2)) and (s1>s2) then exit(true); exit(false);end; function divid(s:ansistring):ansistring;var i :longint; len :longint; ss :ansistring;begin fillchar(a,sizeof(a),0); len:=length(s); for i:=1 to len do a[(len-i) div 7+1]:=a[(len-i) div 7+1]*10+ord(s[i])-48; len:=(len+6) div 7; for i:=len downto 2 do if a[i] mod 2=0 then a[i]:=a[i] div 2 else begin a[i]:=a[i] div 2; a[i-1]:=a[i-1]+10000000; end; a[1]:=a[1] div 2; divid:=''; for i:=len downto 1 do begin str(a[i],ss); if a[i]<1000000 then divid:=divid+'0'; if a[i]<100000 then divid:=divid+'0'; if a[i]<10000 then divid:=divid+'0'; if a[i]<1000 then divid:=divid+'0'; if a[i]<100 then divid:=divid+'0'; if a[i]<10 then divid:=divid+'0'; divid:=divid+ss; end; while (divid[1]='0') and (length(divid)>1) do delete(divid,1,1);end; function jian(s1,s2:ansistring):ansistring;var len1, len2 :longint; ss :ansistring; i :longint;begin fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); fillchar(c,sizeof(c),0); len1:=length(s1); for i:=1 to len1 do a[(len1-i) div 7+1]:=a[(len1-i) div 7+1]*10+ord(s1[i])-48; len2:=length(s2); for i:=1 to len2 do b[(len2-i) div 7+1]:=b[(len2-i) div 7+1]*10+ord(s2[i])-48; len1:=(len1+6) div 7; len2:=(len2+6) div 7; for i:=1 to len1 do begin c[i]:=c[i]+a[i]-b[i]; if c[i]<0 then begin c[i]:=c[i]+10000000; c[i+1]:=c[i+1]-1; end; end; jian:=''; for i:=len1 downto 1 do begin str(c[i],ss); if c[i]<1000000 then jian:=jian+'0'; if c[i]<100000 then jian:=jian+'0'; if c[i]<10000 then jian:=jian+'0'; if c[i]<1000 then jian:=jian+'0'; if c[i]<100 then jian:=jian+'0'; if c[i]<10 then jian:=jian+'0'; jian:=jian+ss; end; while (jian[1]='0') and (length(jian)>1) do delete(jian,1,1);end; function mul(s:ansistring):ansistring;var len :longint; i :longint; ss :ansistring;begin len:=length(s); fillchar(a,sizeof(a),0); for i:=1 to len do a[(len-i) div 7+1]:=a[(len-i) div 7+1]*10+ord(s[i])-48; len:=(len+6) div 7; for i:=1 to len do a[i]:=a[i]*2; for i:=1 to len do begin a[i+1]:=a[i+1]+a[i] div 10000000; a[i]:=a[i] mod 10000000; end; inc(len); mul:=''; for i:=len downto 1 do begin str(a[i],ss); if a[i]<1000000 then mul:=mul+'0'; if a[i]<100000 then mul:=mul+'0'; if a[i]<10000 then mul:=mul+'0'; if a[i]<1000 then mul:=mul+'0'; if a[i]<100 then mul:=mul+'0'; if a[i]<10 then mul:=mul+'0'; mul:=mul+ss; end; while (mul[1]='0') and (length(mul)>1) do delete(mul,1,1);end; begin readln(s1); while (s1[1]='0') and (length(s1)>1) do delete(s1,1,1); readln(s2); while (s2[1]='0') and (length(s2)>1) do delete(s2,1,1); doit:=0; while s1<>s2 do begin if ord(s1[length(s1)]) mod 2=0 then f1:=true else f1:=false; if ord(s2[length(s2)]) mod 2=0 then f2:=true else f2:=false; if f1 and f2 then begin s1:=divid(s1); s2:=divid(s2); inc(doit); end else begin if f1 then s1:=divid(s1); if f2 then s2:=divid(s2); if (not f1) and (not f2) then if max(s1,s2) then s1:=jian(s1,s2) else s2:=jian(s2,s1); end; end; ans:=s1; for i:=1 to doit do ans:=mul(ans); writeln(ans);end.