時間限制: 1 Sec 内存限制: 128 MB
題目描述
分别求兩個整數的最大公約數和最小公倍數
輸入
兩個整數 範圍是 [1, 10000]
輸出
最大公約數 最小公倍數
樣例輸入 Copy
6 15
樣例輸出 Copy
3 30
提示
歐幾裡德算法
歐幾裡德算法又稱輾轉相除法,用于計算兩個整數a,b的最大公約數。
基本算法:設a=qb r,其中a,b,q,r都是整數,則gcd(a,b)=gcd(b,r),即gcd(a,b)=gcd(b,a%b)。
第一種證明:
a可以表示成a = kb r,則r = a mod b
假設d是a,b的一個公約數,則有
d|a, d|b,而r = a - kb,因此d|r
因此d是(b,a mod b)的公約數
假設d 是(b,a mod b)的公約數,則
d | b , d |r ,但是a = kb r
因此d也是(a,b)的公約數
因此(a,b)和(b,a mod b)的公約數是一樣的,其最大公約數也必然相等,得證
第二種證明:
要證歐幾裡德算法成立,即證: gcd(a,b)=gcd(b,r),其中 gcd是取最大公約數的意思,r=a mod b
下面證 gcd(a,b)=gcd(b,r)
設 c是a,b的最大公約數,即c=gcd(a,b),則有 a=mc,b=nc,其中m,n為正整數,且m,n互為質數
由 r= a mod b可知,r= a- qb 其中,q是正整數,
則 r=a-qb=mc-qnc=(m-qn)c
b=nc,r=(m-qn)c,且n,(m-qn)互質(假設n,m-qn不互質,則n=xd, m-qn=yd 其中x,y,d都是正整數,且d>1
則a=mc=(qx y)dc, b=xdc,這時a,b 的最大公約數變成dc,與前提矛盾,
所以n ,m-qn一定互質)
則gcd(b,r)=c=gcd(a,b)
得證。
算法的實現:
最簡單的方法就是應用遞歸算法,代碼如下:
1 int gcd(int a,int b)
2 {
3 if(b==0)
4 return a;
5 return
6 gcd(b,a%b);
7 }
代碼可優化如下:
1 int gcd(int a,int b)
2 {
3 return b ? gcd(b,a%b) : a;
4 }
當然你也可以用疊代形式:
1 int Gcd(int a, int b)
2 {
3 while(b != 0)
4 {
5 int r = b;
6 b = a % b;
7 a = r;
8 }
9 return a;
10 }
V
V
V
V
V
V
V
V
V
V
V
V
V
解題:
#include<bits/stdc .h> using namespace std; int gcd(int a,int b) { if(b == 0) return a; return gcd(b,a%b); } int lcm(int a,int b) { return a*b/gcd(a,b); } int main() { int a,b; cin>>a>>b; cout<<gcd(a,b)<<" "<<lcm(a,b); return 0; }
,更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!