\(Description:\)

写高精的\(gcd(a,b)\)

\(Sample\) \(Input\):

12

54

\(Sample\) \(Output\)：

6

题意简介明了，然而代码。。。很长。。。。。。。。。。。。

一开始单纯的以为可以直接高精过，用更相减损术做gcd，结果wei大了。

敲了一个压了八位的高精，又wei了。

我开始思考。。。

事实证明我得写正解？

（事实是我重载小于号时是从前往后判的。。。。。

但是无知的我开始看题解：

对于更相减损术的优化：

• a是偶数，b是偶数 那么\(gcd(a,b)=gcd(a/2,b/2)*2\)

• a是偶数，b是奇数 那么\(gcd(a,b)=gcd(a /2,b)\)

• a是奇数，b是偶数 那么\(gcd(a,b)=gcd(a,b/2)\)

证明：（我喜欢口糊，大量文字注意！！！

• 1->显然
• 2->显然
• 3->显然

真

大量文字。。。。。。

其实都挺好理解的，那么知道了这三条性质，就可以优化了

时间复杂度

\(O(我不知道)\)

这是什么神仙复杂度。。。。。。

附上写了一个晚上的高精。。。

#include
    
     #define int long longusing namespace std;const int MAXN=100000,B=100000000,MAXM=3000;int A[MAXN+5];namespace Huge_int {    using namespace std;    struct huge_int {        int n;        int a[MAXM+5];        inline void clear() { memset(a,0,sizeof(a));n=0; }        inline void work() { while(n>1 && !a[n]) n--; }        inline huge_int rd() {            memset(A,0,sizeof(A));            clear();            char ch=getchar();            while(ch<'0' || ch>'9') ch=getchar();            while(ch<='9' && ch>='0') A[++n]=ch-'0',ch=getchar();            for(int i=1;i+i<=n;++i) swap(A[i],A[n-i+1]);            for(int i=1;i<=n;i+=8){                int j=(i+7)/8;                a[j]=(A[i]+A[i+1]*10+A[i+2]*100+A[i+3]*1000+A[i+4]*10000+A[i+5]*100000+A[i+6]*1000000+A[i+7]*10000000);            }            n=(n+7)/8;            return *this;        }        inline huge_int wrt() const {            printf("%lld",a[n]);            for(int i=n-1;i>=1;--i) printf("%08lld",a[i]);            putchar('\n');            return *this;        }        inline bool operator < (const huge_int &nt) const {            if(n
     
      nt.n) return 0;            for(int i=n;i>=1;--i)                if(a[i]!=nt.a[i])return a[i]
      
        (const huge_int &nt) const {            return nt<*this;        }        inline bool operator != (const huge_int &nt) const {            return (*this
       
        =1;--i){                x=x*B+a[i];                tmp.a[i]=x/nt;                x%=nt;            }            tmp.work();            return tmp;        }        inline huge_int operator += (const huge_int &nt) { return *this=*this+nt; }        inline huge_int operator -= (const huge_int &nt) { return *this=*this-nt; }        inline huge_int operator *= (const huge_int &nt) { return *this=*this*nt; }        inline huge_int operator /= (const int      &nt) { return *this=*this/nt; }    };    inline huge_int gcd(huge_int a,huge_int b) {        int na=0,nb=0;        while(!(a.a[1]&1)) na++,a/=2;        while(!(b.a[1]&1)) nb++,b/=2;        int x=min(na,nb);        while(a!=b){            if(a