http://www.lydsy.com/JudgeOnline/problem.php?id=1876
Description
Sheng bill有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的GCD（最大公约 数）！因此他经常和别人比
赛计算GCD。有一天Sheng bill很嚣张地找到了你，并要求和你比 赛，但是输给Sheng bill岂不是很丢脸！所以你
决定写一个程序来教训他。
Input
共两行： 第一行：一个数A。 第二行：一个数B。
0 < A , B ≤ 10 ^ 10000。
Output
一行，表示A和B的最大公约数。
Sample Input
12
54
54
Sample Output
6
——————————————————————————————————
如果你会写大整数除法，请跳过这个博客。
要做这道题：
1.我们要压位，对于压位默认看博客的人已经会了，如果不会请baidu。
2.我们需要三个gcd的应用
1.gcd(a,b)=k*gcd(a/k,b/k)(a%k==0,b%k==0)
2.gcd(a,b)=gcd(a/k,b)(a%k==0&&b%k!=0)
3.gcd(a,b)=gcd(b,a-b)(a>b)
然后我们每次进行3操作的时候，用1和2操作来预先分离出来k，减少计算量。
这里取k=2，我们发现这种操作有着很妙的优化：
对于每次操作3，如果是：
1.至少一个偶数，那么就1或2操作，至少减少了其中一个数一半的大小。
2.无偶数，则3操作之后一定能变成1情况。
所以我们大概是能减少一半的运算量，这明显十分的妙！
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll big=1e9;
const int p=;
const int N=;
char s1[N],s2[N];
ll a[N],b[N];
int la=,lb=;
inline int pan(){
if(la>lb)return ;
if(la<lb)return ;
for(int i=la-;i>=;i--){
if(a[i]>b[i])return ;
if(a[i]<b[i])return ;
}
return ;
}
void diva(){
for(int i=la-;i>=;i--){
if(!(a[i]&))a[i]>>=;
else{
a[i-]+=big;
a[i]>>=;
}
}
if(!a[la-])la--;
return;
}
void divb(){
for(int i=lb-;i>=;i--){
if(!(b[i]&))b[i]>>=;
else{
b[i-]+=big;
b[i]>>=;
}
}
if(!b[lb-])lb--;
return;
}
int change(char s[],ll n[]){
char temp[N];
int l=strlen(s),cur=;
while(l/p){
strncpy(temp,s+l-p,p);
n[cur++]=atoi(temp);
l-=p;
}
if(l){
memset(temp,,sizeof(temp));
strncpy(temp,s,l);
n[cur++]=atoi(temp);
}
return cur;
}
void init(){
scanf("%s%s",s1,s2);
la=change(s1,a);
lb=change(s2,b);
return;
}
int k_2=;
void gcd(){
while(){
int a_2=,b_2=;
while(!(a[]&)){diva();a_2++;}
while(!(b[]&)){divb();b_2++;}
k_2+=min(a_2,b_2);
int pi=pan();
if(pi==){
for(int i=;i<la;i++){
if(a[i]<b[i]){
a[i]+=big;
a[i+]--;
}
a[i]=a[i]-b[i];
}
for(int i=la-;i>=;i--){
if(a[i])break;
else la--;
}
}else if(pi==){
for(int i=;i<lb;i++){
if(b[i]<a[i]){
b[i]+=big;
b[i+]--;
}
b[i]=b[i]-a[i];
}
for(int i=lb-;i>=;i--){
if(b[i])break;
else lb--;
}
}else return;
}
return;
}
int main(){
init();
gcd();
for(int i=;i<=k_2;i++){
for(int j=;j<la;j++){
a[j]<<=;
}
for(int j=;j<la;j++){
if(a[j]>big){
a[j+]+=a[j]/big;
a[j]%=big;
if(j+>=la)la++;
}
}
}
printf("%lld",a[la-]);
for(int i=la-;i>=;i--){
printf("%0*lld",p,a[i]);
}
printf("\n");
return ;
}