[SDOI2009]SuperGCD

Time Limit:4000MS Memory Limit:65536K
Total Submit:34 Accepted:6
Case Time Limit:1000MS

Description

Sheng bill有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的GCD（最大公约
数）！因此他经常和别人比赛计算GCD。有一天Sheng bill很嚣张地找到了你，并要求和你比
赛，但是输给Sheng bill岂不是很丢脸！所以你决定写一个程序来教训他。

Input

共两行：
第一行：一个数A。
第二行：一个数B。

Output

一行，表示A和B的最大公约数。

Sample Input

Sample Output

Hint

对于20%的数据，0 < A , B ≤ 10 ^ 18。
对于100%的数据，0 < A , B ≤ 10 ^ 10000。

Source

Day1
总算AC了这题，感谢GCD。。。
然后是算法。。。TMD八中OJ居然没有Java。。。。只好自己写高精度，算法是这样的。。
设这两个数是A，B
那么若2|A和B （A，B）=2（A/2,B/2）。。
若2|A且2不整除B， (A,B)=(A/2,B)..
若A和B都是奇数，设A<B，（A,B）=(A,B-A)…
关键是一般的高精度超时很严重啊。。
于是压位，我压了10位。。结果因为Long Long的问题WA了几次。。。
然后把所有的2放在一起乘。。。
就很快了。。。
Orz。sevenk神牛。。
Code：

#include<cstdio>#include<cstring>#include<iostream>#define Rep(i,n) for(int i=0;i<n;i++)using namespace std;typedef unsigned long long ull;const int maxn=10000+10,L=10;const ull m=1e10;char C[maxn+10];ull P[L];struct BigInt{ ull H[maxn/L+1];int l; BigInt() { memset(H,0,sizeof(H));l=0; } void divide() { ull d=0; for(int i=l;i>=0;i–) { d*=m;d+=H[i]; H[i]=d/2;d%=2; } while(l&&!H[l])l–; } int mod() { return H[0]%2; } void operator*=(int x) { ull d=0; for(int i=0;i<=l;i++) { d+=H[i]*x;H[i]=d%m; d/=m; } while(d)H[++l]=d%m,d/=m; } void operator-=(const BigInt&o) { ull d=0; for(int i=0;i<=l;i++) { H[i]-=d; if(H[i]<o.H[i])H[i]+=m,d=1; else d=0; H[i]-=o.H[i]; } while(l&&!H[l])l–; } void ReadIn() { memset(C,0,sizeof(C)); scanf("%s",C);int s=0;l=0;ull a=0; for(int i=strlen(C)-1;i>=0;i–) { a+=(C[i]-‘0’)*P[s++]; if(s==L)H[l++]=a,s=0,a=0; } if(!s)l–;else H[l]=a; } void Print() { printf("%I64d",H[l]); for(int i=l-1;i>=0;i–)printf("%010I64d",H[i]); } bool operator<(const BigInt&o)const { if(l!=o.l)return l<o.l; for(int i=l;i>=0;i–) { if(H[i]<o.H[i])return true; if(H[i]>o.H[i])return false; } } bool iszero()const{return l==0&&H[l]==0;}}A[2];int main(){ freopen("in","r",stdin); P[0]=1;Rep(i,L-1)P[i+1]=P[i]*10; A[0].ReadIn();A[1].ReadIn(); int a=0,b=1,c=0; while(true) { if(A[b]<A[a])a^=b^=a^=b; //A[a].Print();printf(",");A[b].Print(); //puts(""); if(A[a].iszero()) { while(c>=16)A[b]*=(1<<16),c-=16; while(c–)A[b]*=2; A[b].Print(); break; } int i=A[a].mod(),j=A[b].mod(); if(!i)A[a].divide(); if(!j)A[b].divide(); if(!i&&!j)c++; if(i&&j)A[b]-=A[a]; }}61254