P2152-[SDOI2009]SuperGCD

  1 // luogu-judger-enable-o2
  2 #include<bits/stdc++.h>
  3 using namespace std;
  4 typedef long long ll;
  5 typedef double db;
  6 #define INF 0x3f3f3f3f
  7 #define _for(i,a,b) for(int i = (a);i < b;i ++)
  8 #define _rep(i,a,b) for(int i = (a);i > b;i --)
  9 
 10 #define MAXL 10000
 11 typedef long long ll;
 12 const int bit=100000000;
 13 struct bign
 14 {
 15     int s[MAXL],len;
 16     bign()
 17     {
 18         memset(s,0,sizeof s);
 19         len=0;
 20     }
 21     void clean()
 22     {
 23         while(len>1&&!s[len-1]) len--;
 24     }
 25     void read()
 26     {
 27         char num[MAXL];
 28         scanf("%s",num);
 29         *this=num;
 30     }
 31     void print()
 32     {
 33         printf("%d",s[len-1]);
 34         for(int i=len-2; i>=0; i--)
 35             printf("%08d",s[i]);
 36         putchar(10);
 37     }
 38     bign operator=(const int &num)
 39     {
 40         int tmp=num;
 41         len=0;
 42         while(tmp)
 43         {
 44             s[len++]=tmp%bit;
 45             tmp/=bit;
 46         }
 47         return *this;
 48     }
 49     bign operator=(const char *num)
 50     {
 51         int up=strlen(num),g=1;
 52         len=0;
 53         for(int i=up-1; i>=0; i--)
 54         {
 55             s[len]+=(num[i]-'0')*g;
 56             if(g==bit/10) len++;
 57             g=((g!=bit/10)?g*10:1);
 58         }
 59         len++;
 60         clean();
 61         return *this;
 62     }
 63     bign operator-(const bign &b)const
 64     {
 65         bign c;
 66         bool g=0;
 67         for(int i=0; i<len; i++)
 68         {
 69             int x=s[i]-g;
 70             if(i<b.len) x-=b.s[i];
 71             if(x>=0) g=0;
 72             else x+=bit,g=1;
 73             c.s[c.len++]=x;
 74         }
 75         c.clean();
 76         return c;
 77     }
 78 
 79     bool operator<(const bign &b)const
 80     {
 81         if(len!=b.len) return len<b.len;
 82         for(int i=len-1; i>=0; i--)
 83             if(s[i]!=b.s[i]) return s[i]<b.s[i];
 84         return false;
 85     }
 86     bool operator>(const bign &b)const
 87     {
 88         if(len!=b.len) return len>b.len;
 89         for(int i=len-1; i>=0; i--)
 90             if(s[i]!=b.s[i]) return s[i]>b.s[i];
 91         return false;
 92     }
 93     bool operator==(const bign &b)const
 94     {
 95       //  if(len!=b.len) return false;
 96         for(int i=0; i<len; i++)
 97             if(s[i]!=b.s[i]) return false;
 98         return true;
 99     }
100 };
101 bign gcd(bign a,bign b)
102 {
103     while(!(a==b))
104     {
105         if(a>b)
106             a = a-b;
107         else
108             b = b-a;
109     }    
110     return a;
111 }
112 int main()
113 {
114     bign a;
115     a.read();
116     bign b;
117     b.read();
118     bign c;
119     c = gcd(a,b);
120     c.print();
121     return 0;
122 }