고정밀

우선 우리는 두 개의 수 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 div2, b div2)
a가 홀수, b가 홀수일 때 유클리드의 법칙에 따라 gcd(a, b)=gcd(a-b, b)(a>b)가 있을 때
그러면 이 문제는 a, b의 범위를 끊임없이 축소하는 것이 되었다.그냥 고정밀이면 돼.물론 데이터가 1, 10^1000일 때는 제목이 양심적으로 그런 데이터가 없다.
 
고정필이 엉망이 되었다.

/**************************************************************

    Problem: 1876

    User: BLADEVIL

    Language: Pascal

    Result: Time_Limit_Exceed

****************************************************************/

 

//By BLADEVIL

var

    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.