P2152-[SDOI2009]SuperGCD

小鱼儿 2023-06-01 08:47 283阅读 0赞

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 }

转载于:https://www.cnblogs.com/Asurudo/p/11452725.html