当前位置: 首页 > >

最大公约数(优化算法)

发布时间:

先看看暴力枚举法求最大公约数、最小公倍数


#include
#include
using namespace std;
int main()
{
long long n1,n2;
cin>>n1>>n2;
long long _min=min(n1,n2),i;
for( i=2;i<=_min;i++)//最大公约数
{
if(n1%i==0&&n2%i==0)
{
cout< break;
}
}
if(i>_min) cout<<"1"< return 0;
}

可以看出暴力枚举方法很方便,但同时也会将太多时间放在判断上,当数很大时,此方法实现起来就很费力了。那可不可用一种效率更高的算法来替代呢?先看看下面的推导公示。


设F(x,y)表示为x,y的最大公约数,取k=x/y,b=x%y,那么x=ky+b,如果一个数能够整除x和y,那么一定可以整除y和b,也就是说,能够整除y和b的数,一定能够整除x和y,所以x和y的公约数和y和b的公约数相同,其最大公约数也相同,则有
F(x,y)=F(y,x%y)(x>=y>0),这样就把求两个数的最大公约数转化为求两个更小的数的公约数,直到其中一个数为0,那么另一个数就是两者的最大公约数。


F(42,30)=F(30,12)=F(12,6)=F(6,0)=6

以上就是辗转相除的思路,更详细的证明读者可以在相关的书籍中找到,但即使这样在求取最大公约数的时候也有缺陷。现在介绍另一种做法,先从公约数的特点入手。
设x=k1x1,y=k1y1,则F(x,y)=k1 F(x1,y1)。
设x=px1,(p为素数且y%p!=0)则F(x,y)=F(x1,y)。
现在取p=2。
若x,y均为偶数,则F(x,y)=2
F(x/2,y/2)。
若x为偶数,y为奇数则F(x,y)=F(x/2,y)。
若x为奇数,y为偶数则F(x,y)=F(x,y/2)。
若x和y同时为奇数,F(x,y)=F(y,x-y)。(两个奇数相减后必定会出现一个偶数)
这种做法的算法复杂度为O(log2(max(x,y)))。


#include
#include
#include
using namespace std;
int isoushu(long x)
{
if(x%2==0) return 1;
else return 0;
}
int fun(long long a,long long b)
{ if(b>a) return fun(b,a);
else if(a==0)return b;


else
{ if(isoushu(a))
if(isoushu(b))
{
return (fun(a>>1,b>>1)<<1);
}
else return fun(a>>1,b);

else
{ if(isoushu(b))
return fun(a,b>>1);
else return (a-b,b);

}


}
}
main()
{
long long a,b;
cin>>a>>b;
cout<
}



友情链接: