P2152题解
题目描述
Sheng bill 有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的最大公约数！因此他经常和别人比赛计算最大公约数。有一天Sheng bill很嚣张地找到了你，并要求和你比赛，但是输给 Sheng bill 岂不是很丢脸！所以你决定写一个程序来教训他。
题解
题解的方法很乱，但我的方法就只是高精度模拟辗转相除，考虑到高精模实在是有些许困难，所以我们用相减更损法取而代之，显然他的复杂度是非常爆炸的。
考虑优化，当两个数非常接近的时候，我们发现，相减的复杂度跟取模的效果是一模一样的。但是当两数数位相差较大时怎么办呢？很简单，我们可以补位。最后注意一下常数带来的影响就可以极限过了！
代码：
#include<bits/stdc++.h>
#define rint register int
using namespace std;
const int N=1e4+100;
string s1,s2;
int l,op;
struct node{
int l,a[N];
inline bool operator < (const node &x)const
{
if(l!=x.l)
return l<x.l;
for(rint i=l;i>=1;i--)
{
if(a[i]!=x.a[i])
return a[i]<x.a[i];
}
return false;
}
inline bool operator == (const node &x)const
{
if(l!=x.l)
return false;
for(rint i=l;i>=1;i--)
{
if(a[i]!=x.a[i])
return false;
}
return true;
}
}a1,a2,z;
inline void gcd()
{
if(a1==a2)
return;
if(a1<a2)
{
if(a2.l>a1.l)
{
op=0,l=a2.l-a1.l;
for(rint i=a2.l;i>=a2.l-a1.l+1;i--)
{
if(a2.a[i]>a1.a[i-l])
{
op=1;
break;
}
else if(a2.a[i]<a1.a[i-l])
{
op=-1;
break;
}
}
if(op==0)
{
for(rint i=a2.l-a1.l;i>=1;i--)
{
if(a2.a[i]!=0)
{
op=1;
break;
}
}
}
if(op==0)
{
a2=a1;
return;
}
if(op==1)
{
for(rint i=a2.l;i>=a2.l-a1.l+1;i--)
z.a[i]=a1.a[i-l];
for(rint i=a2.l-a1.l;i>=1;i--)
z.a[i]=0;
z.l=a2.l;
}
if(op==-1)
{
for(rint i=a2.l-1;i>=a2.l-a1.l;i--)
z.a[i]=a1.a[i-l+1];
for(rint i=a2.l-a1.l-1;i>=1;i--)
z.a[i]=0;
z.l=a2.l-1;
}
}
else
{
z=a1;
}
while(z<a2)
{
for(rint i=1;i<=z.l;i++)
{
a2.a[i]-=z.a[i];
if(a2.a[i]<0)
a2.a[i]+=10,a2.a[i+1]-=1;
}
for(rint i=a2.l;i>=1;i--)
{
if(a2.a[i]==0)
a2.l=i-1;
else
break;
}
}
gcd();
}
else
{
if(a1.l>a2.l)
{
op=0,l=a1.l-a2.l;
for(rint i=a1.l;i>=a1.l-a2.l+1;i--)
{
if(a1.a[i]>a2.a[i-l])
{
op=1;
break;
}
else if(a1.a[i]<a2.a[i-l])
{
op=-1;
break;
}
}
if(op==0)
{
for(rint i=a1.l-a2.l;i>=1;i--)
{
if(a1.a[i]!=0)
{
op=1;
break;
}
}
}
if(op==0)
{
a1=a2;
return;
}
if(op==1)
{
for(rint i=a1.l;i>=a1.l-a2.l+1;i--)
z.a[i]=a2.a[i-l];
for(rint i=a1.l-a2.l;i>=1;i--)
z.a[i]=0;
z.l=a1.l;
}
if(op==-1)
{
for(rint i=a1.l-1;i>=a1.l-a2.l;i--)
z.a[i]=a2.a[i-l+1];
for(rint i=a1.l-a2.l-1;i>=1;i--)
z.a[i]=0;
z.l=a1.l-1;
}
}
else
{
z=a2;
}
while(z<a1)
{
for(rint i=1;i<=z.l;i++)
{
a1.a[i]-=z.a[i];
if(a1.a[i]<0)
a1.a[i]+=10,a1.a[i+1]-=1;
}
for(rint i=a1.l;i>=1;i--)
{
if(a1.a[i]==0)
a1.l=i-1;
else
break;
}
}
gcd();
}
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>s1>>s2;
a1.l=s1.size();
a2.l=s2.size();
for(rint i=0;i<a1.l;i++)
a1.a[a1.l-i]=s1[i]-'0';
for(rint i=0;i<a2.l;i++)
a2.a[a2.l-i]=s2[i]-'0';
gcd();
for(rint i=a1.l;i>=1;i--)
cout<<a1.a[i];
return 0;
}