http://www.lydsy.com/JudgeOnline/problem.php?id=1876 https://www.luogu.org/problem/show?pid=2152
其实就是高精度gcd，因为辗转相除要试乘很麻烦而且耗时间（我是不会告诉你我其实是不会高精度除法），有个更相减损法很好用：
可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。——《九章算术》
白话文翻译如下：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
我们其实可以进一步优化，若两个是偶数则同除以2，结果乘以2，若为一奇一偶则偶数除以2，结果不变，若为两个奇数才相减 这样理论上说能够通过此题了，但是还是有些小问题，比如：
递归式做法。。。爆栈大大的有。。。没压位。。。TLE大大的有。。。（据说此题要想在LuoguAC要压18位害怕。。。代码太长错误找半天没找出来。。。（QAQ就是我。。。） #include<bits/stdc++.h> #define ll long long using namespace std; struct bigint{ ll c[1001];bool b; }a,b,c,p,tmp,ans; bigint pp,two; bool flag=0; char sa[20001],sb[20001]; inline void shuchu(bigint a){ ll rp,i; for(i=a.c[0];i>0;--i){ if(i<a.c[0])printf("8lld",a.c[i]); else printf("%lld",a.c[i]); } } inline int bj(bigint a,bigint b){ ll i; if(a.c[0]>b.c[0])return 1; if(a.c[0]<b.c[0])return 0; for(i=a.c[0];i>0;--i)if(a.c[i]>b.c[i])return 1; else if(a.c[i]<b.c[i])return 0; return 2; } inline bigint cheng(bigint a,bigint b){ ll i,j; memset(tmp.c,0,sizeof tmp.c); for(i=1;i<=a.c[0];++i) for(j=1,tmp.c[0]=i-1;j<=b.c[0];++j)tmp.c[++tmp.c[0]]+=b.c[j]*a.c[i]; for(i=1;i<=tmp.c[0];++i)if(tmp.c[i]>999999999999999999){ if(tmp.c[tmp.c[0]]>999999999999999999)tmp.c[0]++; tmp.c[i+1]+=tmp.c[i]/1000000000000000000; tmp.c[i]%=1000000000000000000; } return tmp; } inline bigint jian(bigint a,bigint b){ ll i; for(i=1;i<=a.c[0];++i){ if(i<=b.c[0])a.c[i]-=b.c[i]; if(a.c[i]<0){ a.c[i+1]--; a.c[i]+=1000000000000000000; } } while(a.c[a.c[0]]==0&&a.c[0]>1)--a.c[0]; return a; } inline bigint chu(bigint a){ ll i,t=0; for(i=a.c[0];i>0;i--){ t=t*1000000000000000000+a.c[i]; a.c[i]=t>>1; t=t&1; } while(!a.c[a.c[0]]&&a.c[0]>1)a.c[0]--; return a; } inline bigint gcd(bigint a,bigint b){ while(1){ if(bj(a,b)==2)return a; if(a.c[0]==1&&a.c[1]==0)return b; if(b.c[0]==1&&b.c[1]==0)return a; if(a.c[1]%2==0&&b.c[1]%2==0){ pp=cheng(pp,two); a=chu(a);b=chu(b); }else if(a.c[1]%2==0)a=chu(a); else if(b.c[1]%2==0)b=chu(b); else{ if(bj(a,b)==1)a=jian(a,b); else b=jian(b,a); } } } inline ll e(ll rp){ if(rp==0)return 1; if(rp==1)return 10; if(rp==2)return 100; if(rp==3)return 1000; if(rp==4)return 10000; if(rp==5)return 100000; if(rp==6)return 1000000; if(rp==7)return 10000000; if(rp==8)return 100000000; if(rp==9)return 1000000000; if(rp==10)return 10000000000; if(rp==11)return 100000000000; if(rp==12)return 1000000000000; if(rp==13)return 10000000000000; if(rp==14)return 100000000000000; if(rp==15)return 1000000000000000; if(rp==16)return 10000000000000000; if(rp==17)return 100000000000000000; } inline void init(){ scanf("%s",sa);scanf("%s",sb); ll i,la=strlen(sa),lb=strlen(sb); if(sa[0]=='0'||sb[0]=='0'){ printf("0");flag=1;return; } a.c[0]=1;ll rp=0; for(i=la-1;i>=0;--i)if(sa[i]>='0'&&sa[i]<='9'){ a.c[a.c[0]]+=(ll)(sa[i]-'0')*e(rp); ++rp;if(rp==18)rp=0; if(rp==0)++a.c[0]; } if(a.c[a.c[0]]==0)--a.c[0]; b.c[0]=1;rp=0; for(i=lb-1;i>=0;--i)if(sb[i]>='0'&&sb[i]<='9'){ b.c[b.c[0]]+=(ll)(sb[i]-'0')*e(rp); ++rp;if(rp==18)rp=0; if(rp==0)++b.c[0]; } if(b.c[b.c[0]]==0)--b.c[0]; } int main() { init(); if(flag)return 0; two.b=1;two.c[0]=1;two.c[1]=2; pp.b=1;pp.c[0]=1;pp.c[1]=1; ans=gcd(a,b); ans=cheng(ans,pp); shuchu(ans); return 0; }