Description
Sheng bill有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的GCD（最大公约 数）！因此他经常和别人比赛计算GCD。有一天Sheng bill很嚣张地找到了你，并要求和你比 赛，但是输给Sheng bill岂不是很丢脸！所以你决定写一个程序来教训他。
Input
共两行： 第一行：一个数A。 第二行：一个数B。
Output
一行，表示A和B的最大公约数。
Sample Input
12
54
54
Sample Output
6
HINT
对于20%的数据，0 < A , B ≤ 10 ^ 18。
对于100%的数据，0 < A , B ≤ 10 ^ 10000。
题解
高精度的模板题，有高精减高精，高精乘单精，高精除单精。
对于更相减损术，有一点可以优化，就是若两者都能整除2，就记录一下，然后除完继续做，如果只有一个能整除2，就直接除掉即可。
最后，我的高精度模板还是很难看啊……
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define M 100000000
using namespace std;
char A[10010],B[10010];
struct shu
{
int l,s[1300];
void operator -= (shu x)
{int i;
for(i=1;i<=l;i++)
{s[i]-=x.s[i];
if(s[i]<0) {s[i]+=M; s[i+1]--;}
}
while(s[l]==0&&l>1) l--;
}
}
a,b,c;
int cnt2=0;
void init()
{
scanf("%s%s",A+1,B+1);
int i,t,j;
char c;
i=strlen(A+1);
while(i>0)
{t=0;
for(j=max(i-7,1);j<=i;j++) t=t*10+(A[j]-'0');
a.s[++a.l]=t; i-=8;
}
i=strlen(B+1);
while(i>0)
{t=0;
for(j=max(i-7,1);j<=i;j++) t=t*10+(B[j]-'0');
b.s[++b.l]=t; i-=8;
}
}
shu operator /(shu x,int y)
{
shu ans;
memset(ans.s,0,sizeof(ans.s));
int i;
for(i=x.l;i>0;i--)
{if(i>1) x.s[i-1]+=(x.s[i]%y)*M;
ans.s[i]=x.s[i]/y;
}
i=x.l;
while(i>1&&ans.s[i]==0) i--;
ans.l=i;
return ans;
}
int cmp(shu x,shu y)
{
if(x.l>y.l) return 1;
else if(x.l<y.l) return 0;
else
{int i;
for(i=x.l;i>0;i--)
{if(x.s[i]<y.s[i]) return 0;
else if(x.s[i]>y.s[i]) return 1;
}
}
return 1;
}
bool check(shu x)
{
if(x.s[1]==0&&x.l==1) return false;
return true;
}
void gcd(shu x,shu y)
{
while(check(x)&&check(y))
{if((x.s[1]%2==0)&&(y.s[1]%2==0))
{cnt2++; x=x/2; y=y/2;
}
else if(x.s[1]%2==0) x=x/2;
else if(y.s[1]%2==0) y=y/2;
else
{if(cmp(x,y)) x-=y;
else y-=x;
}
}
if(!check(x)) c=y;
else c=x;
}
shu operator *(shu x,int y)
{
shu ans;
memset(ans.s,0,sizeof(ans.s));
int i;
for(i=1;i<=x.l;i++) ans.s[i]=x.s[i]*y;
for(i=1;i<=x.l;i++)
{if(ans.s[i]>=M)
{ans.s[i+1]+=ans.s[i]/M;
ans.s[i]%=M;
}
}
i=x.l+1;
while(ans.s[i]>0)
{if(ans.s[i]>=M)
{ans.s[i+1]+=ans.s[i]/M;
ans.s[i]%=M;
}
i++;
}
ans.l=i-1;
return ans;
}
int main()
{
init();
gcd(a,b);
while(cnt2--) c=c*2;
printf("%d",c.s[c.l]);
for(int i=c.l-1;i>0;i--) printf("%08d",c.s[i]);
printf("\n");
return 0;
}