1630：SuperGCD
时间限制: 1000 ms 内存限制: 524288 KB
【题目描述】
来源：SDOI 2009
Sheng Bill 有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的 GCD（最大公约数）！因此他经常和别人比赛计算 GCD。有一天 Sheng Bill 很嚣张地找到了你，并要求和你比赛，但是输给 Sheng Bill 岂不是很丢脸！所以你决定写一个程序来教训他。
【输入】
输入共两行，第一行一个数 A，第二行一个数 B。
【输出】
一行，表示 A 和 B 的最大公约数。
【输入样例】
12
54
【输出样例】
6
【提示】
数据范围与提示：
对于全部数据，0<A,B≤10。
sol：就是这道题的加强版，方法几乎一样，只是压4位过不去，要压八位，但是最后涉及到乘法需要long long，又会变慢，所以要记录要乘的 2 的个数，在最后统计答案的时候一个个乘进去，我复杂度非常劣
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
ll s=;
bool f=;
char ch=' ';
while(!isdigit(ch))
{
f|=(ch=='-'); ch=getchar();
}
while(isdigit(ch))
{
s=(s<<)+(s<<)+(ch^); ch=getchar();
}
return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
if(x<)
{
putchar('-'); x=-x;
}
if(x<)
{
putchar(x+''); return;
}
write(x/);
putchar((x%)+'');
return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
inline void Read_S(char *S)
{ int Len=;
char ch=' ';
while(!isdigit(ch))
{
ch=getchar();
}
while(ch=='')
{
ch=getchar();
}
while(isdigit(ch))
{
S[++Len]=ch; ch=getchar();
}
return;
}
const int N=;
const int Base=,Power=;
char SX[N],SY[N];
struct BigNum
{
int a[N];
BigNum()
{
memset(a,,sizeof a);
}
BigNum(char *S)
{
memset(a,,sizeof a);
int i,bb,Pos=,Len=strlen(S+);
a[]=(Len-)/Power+;
for(i=;i<=Len;i++)
{
if((i-)%Power==)
{
Pos++; bb=;
}
a[Pos]+=bb*(S[i]-'');
bb*=;
}
}
inline void Print()
{
write(a[a[]]);
int i;
for(i=a[]-;i>=;i--)
{
if(a[i]<) putchar('');
if(a[i]<) putchar('');
if(a[i]<) putchar('');
if(a[i]<) putchar('');
if(a[i]<) putchar('');
if(a[i]<) putchar('');
if(a[i]<) putchar('');
write(a[i]);
}
}
#define P(x) x.Print(),putchar(' ')
#define Pl(x) x.Print(),putchar('\n')
};
BigNum X,Y;
//BigNum Ans;
inline bool operator<(const BigNum &p,const BigNum &q)
{
if(p.a[]!=q.a[]) return p.a[]<q.a[];
int i;
for(i=p.a[];i>=;i--) if(p.a[i]!=q.a[i])
{
return p.a[i]<q.a[i];
}
return false;
}
inline bool operator==(const BigNum &p,const BigNum &q)
{
if(p.a[]!=q.a[]) return false;
int i;
for(i=p.a[];i>=;i--) if(p.a[i]!=q.a[i])
{
return false;
}
return true;
}
inline BigNum operator-(const BigNum &p,const BigNum &q)
{
int i;
BigNum ans=p;
for(i=;i<=q.a[];i++)
{
ans.a[i]-=q.a[i];
if(ans.a[i]<)
{
ans.a[i]+=Base;
ans.a[i+]--;
}
}
while((!ans.a[ans.a[]])&&ans.a[]) ans.a[]--;
return ans;
}
inline BigNum operator*(const BigNum &p,const BigNum &q)
{
int i,j;
BigNum ans; ans.a[]=max(p.a[],q.a[]);
for(i=;i<=p.a[];i++)
{
for(j=;j<=q.a[];j++)
{
ans.a[i+j-]+=p.a[i]*q.a[j];
ans.a[i+j]+=ans.a[i+j-]/Base;
ans.a[i+j-]%=Base;
}
}
while(ans.a[ans.a[]+]) ans.a[]++;
while(!ans.a[ans.a[]]) ans.a[]--;
return ans;
}
inline bool Judge_Ou(BigNum p)
{
if(!p.a[]) return ;
return (p.a[]&)?:;
}
inline BigNum Div2(BigNum p)
{
BigNum ans;
ans.a[]=p.a[];
int i;
for(i=p.a[];i>=;i--)
{
ans.a[i]+=(p.a[i]>>);
if(p.a[i]&) p.a[i-]+=Base;
}
while(!ans.a[ans.a[]]) ans.a[]--;
return ans;
}
inline BigNum Mul2(BigNum p)
{
BigNum ans;
ans.a[]=p.a[];
int i;
for(i=;i<=p.a[];i++)
{
p.a[i]<<=;
if(p.a[i]>Base)
{
ans.a[i+]+=p.a[i]/Base;
p.a[i]%=Base;
}
ans.a[i]+=p.a[i];
}
while(ans.a[ans.a[]+]) ans.a[]++;
return ans;
}
int main()
{
int i;
Read_S(SX);
reverse(SX+,SX+strlen(SX+)+);
X=BigNum(SX);
Read_S(SY);
reverse(SY+,SY+strlen(SY+)+);
Y=BigNum(SY);
// Ans.a[0]=Ans.a[1]=1;
int Ges2=;
while(!(X==Y))
{
// P(X); Pl(Y);
bool BoX=Judge_Ou(X),BoY=Judge_Ou(Y);
if(BoX)
{
if(BoY)
{
X=Div2(X); Y=Div2(Y);
// Ans=Mul2(Ans);
Ges2++;
}
else
{
X=Div2(X);
}
}
else
{
if(BoY)
{
Y=Div2(Y);
}
else
{
BigNum p,q;
if(X<Y) p=Y,q=X;
else p=X,q=Y;
X=p-q; Y=q;
}
}
}
for(i=;i<=Ges2;i++) X=Mul2(X);
// Ans=Ans*X;
// Pl(Ans);
Pl(X);
return ;
}