時間限制: 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每日頭條，我们将持续为您更新最新资讯!