链接：http://acm.ocrosoft.com/problem.php?cid=1702&pid=0
题目描述
给出两个正整数 A,B，求它们的最大公约数。
输入
输入共两行，第一行一个正整数 A，第二行一个正整数 B。
对于 60% 的数据，1≤A,B≤1018；
对于 100% 的数据，1≤A,B≤103000。
输出
在第一行输出一个整数，表示 A,B 的最大公约数。
样例输入
18
24
样例输出
6
思路：
这道题是一道大数的约数题，用普通的辗转相除法肯定会TLE因此我们要用大数的转转相除法
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 1000000000
using namespace std;
char ch1[10005],ch2[10005];
int la,lb,cnt;
struct data{
int a[1205],l;
}a,b;//建立结构体，a数组存数字，l表示长度
bool com()//比较函数,比较两个数大小
{
if(a.l<b.l)
return 0;
if(a.l>b.l)
return 1;
for(int i=a.l;i>0;--i)
if(a.a[i]>b.a[i])
return 1;
else if(a.a[i]<b.a[i])
return 0;
return 1;
}
void print(data a)//输出函数
{
while(a.a[a.l]==0)
a.l--;
for(int i=a.l;i>0;--i)
if(i==a.l)
printf("%d",a.a[i]);
else printf("%09d",a.a[i]);
}
inline data sub(data a,data b)//高精度辗转相除法
{
int k;
data c;//用于记录中间值，以及最后输出结果
for(int i=1;i<=1200;++i)
{
if(i<=b.l)
c.a[i]=a.a[i]-b.a[i];
else if(i<=a.l)
c.a[i]=a.a[i];
else
c.a[i]=0;
if(c.a[i]<0)
{
c.a[i]+=inf;
a.a[i+1]--;
}
}
c.l=a.l;
while(c.a[c.l]==0&&c.l)//除去前导零
c.l--;
return c;
}
void diva()//去2操作
{
for(int i=1;i<=a.l;i++)
{
if(a.a[i]&1)a.a[i-1]+=inf/2;
a.a[i]>>=1;
}
if(!a.a[a.l])
a.l--;
}
void divb()
{
for(int i=1;i<=b.l;i++)
{
if(b.a[i]&1)b.a[i-1]+=inf/2;
b.a[i]>>=1;
}
if(!b.a[b.l])
b.l--;
}
void mul()//重新将2加回
{
for(int i=a.l;i>0;i--)
{
a.a[i]<<=1;
a.a[i+1]+=a.a[i]/inf;
a.a[i]%=inf;
}
while(a.a[a.l]>0)
a.l++;
for(int i=b.l;i>0;i--)
{
b.a[i]<<=1;
b.a[i+1]+=b.a[i]/inf;
b.a[i]%=inf;
}
while(b.a[b.l]>0)
b.l++;
}
int main()
{
scanf("%s%s",ch1+1,ch2+1);
la=strlen(ch1+1);
lb=strlen(ch2+1);
if(la%9)
a.l=la/9+1;//以九位为单位，分割大数
else
a.l=la/9;
if(lb%9)
b.l=lb/9+1;
else
b.l=lb/9;
for(int i=1;i<=a.l;++i)
{
int k1=max(1,la-i*9+1),k2=la-(i-1)*9;
for(int j=k1;j<=k2;++j)
a.a[i]=a.a[i]*10+ch1[j]-'0';
}
for(int i=1;i<=b.l;++i)
{
int k1=max(1,lb-i*9+1),k2=lb-(i-1)*9;
for(int j=k1;j<=k2;++j)
b.a[i]=b.a[i]*10+ch2[j]-'0';
}
while(1)
{
if((a.a[1]%2==0)&&(b.a[1]%2==0))
{
diva();
divb();
cnt++;
}
else if((a.a[1]%2==0))
diva();
else if((b.a[1]%2==0))
divb();
if(com())
{
a=sub(a,b);
if(!a.l)
{
while(cnt--)
mul();
print(b);
break;
}
}
else
{
b=sub(b,a);
if(!b.l)
{
while(cnt--)
mul();
print(a);
break;
}
}
}
return 0;
京公网安备 11010502036488号