Description

Sheng bill有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的GCD（最大公约 数）！因此他经常和别人比

赛计算GCD。有一天Sheng bill很嚣张地找到了你，并要求和你比 赛，但是输给Sheng bill岂不是很丢脸！所以你

决定写一个程序来教训他。

Input

共两行： 第一行：一个数A。 第二行：一个数B。

0 < A , B ≤ 10 ^ 10000。

Output

一行，表示A和B的最大公约数。

Sample Input

12

54

Sample Output

6

——————————————————————————————————

如果你会写大整数除法，请跳过这个博客。

要做这道题：

1.我们要压位，对于压位默认看博客的人已经会了，如果不会请baidu。

2.我们需要三个gcd的应用

　　1.gcd(a,b)=k*gcd(a/k,b/k)(a%k==0,b%k==0)

　　2.gcd(a,b)=gcd(a/k,b)(a%k==0&&b%k!=0)

　　3.gcd(a,b)=gcd(b,a-b)(a>b)

然后我们每次进行3操作的时候，用1和2操作来预先分离出来k，减少计算量。

这里取k=2，我们发现这种操作有着很妙的优化：

对于每次操作3，如果是：

　　1.至少一个偶数，那么就1或2操作，至少减少了其中一个数一半的大小。

　　2.无偶数，则3操作之后一定能变成1情况。

所以我们大概是能减少一半的运算量，这明显十分的妙！

#include
     
        #include
      
         #include
       
          #include
        
         #include
         
          using namespace std;typedef long long ll;const ll big=1e9;const int p=9;const int N=10010;char s1[N],s2[N];ll a[N],b[N];int la=0,lb=0;inline int pan(){    if(la>lb)return 0;    if(la
          
           =0;i--){ if(a[i]>b[i])return 0; if(a[i]
           
            =0;i--){ if(!(a[i]&1))a[i]>>=1; else{ a[i-1]+=big; a[i]>>=1; } } 　　if(!a[la-1])la--; return;}void divb(){ for(int i=lb-1;i>=0;i--){ if(!(b[i]&1))b[i]>>=1; else{ b[i-1]+=big; b[i]>>=1; } } if(!b[lb-1])lb--; return;}int change(char s[],ll n[]){ char temp[N]; int l=strlen(s),cur=0; while(l/p){ strncpy(temp,s+l-p,p); n[cur++]=atoi(temp); l-=p; } if(l){ memset(temp,0,sizeof(temp)); strncpy(temp,s,l); n[cur++]=atoi(temp); } return cur;}void init(){ scanf("%s%s",s1,s2); la=change(s1,a); lb=change(s2,b); return;}int k_2=0;void gcd(){ while(233){ int a_2=0,b_2=0; while(!(a[0]&1)){diva();a_2++;} while(!(b[0]&1)){divb();b_2++;} k_2+=min(a_2,b_2); int pi=pan(); if(pi==0){ for(int i=0;i
            
             =0;i--){ if(a[i])break; else la--; } }else if(pi==1){ for(int i=0;i
             
              =0;i--){ if(b[i])break; else lb--; } }else return; } return;}int main(){ init(); gcd(); for(int i=1;i<=k_2;i++){ for(int j=0;j
              
               big){ a[j+1]+=a[j]/big; a[j]%=big; if(j+1>=la)la++; } } } printf("%lld",a[la-1]); for(int i=la-2;i>=0;i--){ printf("%0*lld",p,a[i]); } printf("\n"); return 0;}