求两个数a和b的最大公约数，可以想到的是从[1,min(a,b)]枚举每个正整数：
#include<iostream>
using namespace std;
int gcd(int a,int b)
{
int ans=1;
for(int i=2;i<=min(a,b);++i)
{
if(a%i==0 && b%i==0)
ans=i;
}
return ans;
}
int main()
{
int a,b;
cin>>a>>b;
cout<<gcd(a,b);
return 0;
}
不过当a和b规模比较大时，这种算法是不够快的。有更快更优雅的算法。
- 首先给出一个定理：
gcd(a,b)=gcd(b,a-b) (a>=b)
证明：
设gcd(a,b)=m (m>=1)
则a%m=0,b%m=0
(a%m-b%m)%m=0
(a-b)%m=0
因为a%m=0,b%m=0,(a-b)%m=0,gcd(a,b)=m
所以gcd(a,b,a-b)=m;
下面证明gcd(b,a-b)=m，然后可以得到gcd(a,b)=gcd(b,a-b)。
设c=a-b
因为gcd(a,b,c)=m;
所以gcd(b,c)!=m的充要条件是存在一个数d (d>=1)使得(b/m)%d=0且(c/m)%d=0且(a/m)%d!=0。
下面用反证法：
设存在这样的d
(c/m)%d=0
((a-b)/m)%d=0
((a/m)-(b/m))%d=0
((a/m)%d-(b/m)%d)%d=0
已知(b/m)%d=0，代入得((a/m)%d)%d=0
又已知(a/m)%d!=0，所以(a/m)%d的结果属于(0,d)
而x属于(0,d)，x%d不可能等于0，因此矛盾。
所以不存在这样的d
所以gcd(b,a-b)=gcd(b,c)=m
gcd(a,b)=gcd(b,a-b) (a>=b) 该定理证明完毕
于是就可以用这个算法来计算，其中gcd(a,0)=a：
#include<iostream>
using namespace std;
int gcd(int a,int b)
{
if(b==0)
return a;
if(a<b)
swap(a,b);
return gcd(b,a-b);
}
int main()
{
int a,b;
cin>>a>>b;
if(a<b)
swap(a,b);
cout<<gcd(a,b);
return 0;
}
当然数据规模大的时候栈可能会溢出，所以改成非递归即可。
还可以更快？（感谢一位同学的证明）
- 再给出第二个定理：
gcd(a,b)=gcd(b,a-k*b) 其中k=0,1,2,3,4...且a>=k*b
这个定理证明同上
- 经化简可得下面这个定理：
gcd(a,b)=gcd(b,a%b)
这就是辗转相除法（欧几里得算法）。
#include<iostream>
using namespace std;
int gcd(int a,int b)
{
if(b==0)
return a;
return gcd(b,a%b);
}
int main()
{
int a,b;
cin>>a>>b;
cout<<gcd(a,b);
return 0;
}