流离之人追逐幻影

用户名：pwj666

访问量：60203

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13954
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：186

你可能喜欢

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

【原理、题解、代码】最大公约数与最小公倍数

　　作者: 流离之人追逐幻影　　　　发表时间：2022-07-20 00:33:05 浏览：186　|　评论：0　

原题链接：[编程入门]最大公约数与最小公倍数

# 题解
##原理
`公式: 两个数的乘积 = 两数的最小公倍数 x 最大公约数`
## 方法
```cpp
int gcd1(int x,int y);//暴力穷举法
int gcd2(int x,int y);//短除法
int gcd3(int x,int y);//辗转相除法（欧几里得算法）
int gcd4(int x,int y);//辗转相减法（更相减损法）【递归】
int gcd5(int x,int y);//辗转相减法（更相减损法）【非递归】
int gcd6(int x,int y);//Stein算法【非递归】
int gcd7(int a, int b);//Stein算法【递归】
```

------------

## 1.暴力穷举法
### 步骤
`从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数。`
###代码
```cpp
//暴力穷举法
int gcd1(int x,int y){

int tmp = fmin(x,y); //把两个数的最小值赋给tmp
	while (1)
	{
		if (x % tmp == 0 && y % tmp == 0)
		{
			break;  
		}
		tmp--;  
	}
	return tmp;
}
```

------------
## 2.短除法
###原理

`把短处号左边的所有质因数和短处号下面的两个数相乘`
![](/image_editor_upload/20220720/20220720120131_39665.png)
`最大公约数：2*2=4,最小公倍数：2*2*2*9=72`
###步骤
`先用这几个数的公约数去除每个数，再用部分数的公约数去除，并把不能整除的数移下来，一直除到所有的商中每两个数都是互质的为止，然后把所有的除数和商连乘起来，所得的积就是这几个数的最小公倍数`
###代码
```cpp
// 短除法
int  gcd2(int x,int y){

int tmp = 1;
	for(int i = 2;i<=x&&i<=y;i++){
		while(x%i==0&&y%i==0){      //while 的用法是用来控制从最低的二开始判断的
			tmp = tmp*i;
			x /= i;
			y /= i;
		}
	}
    return tmp;
}
```
------------
##3.辗转相除法（欧几里得算法）
###步骤
```cpp
1.前提：设两数为x,y设其中x 做被除数,y做除数，remainder为余数
2.大数放big中、小数放small中；
3.求big/small的余数；
4.若remainder=0则small为最大公约数；
5.如果remainder!=0则把small的值给big、remainder的值给small；
6.返回第二步；
```
###代码
```cpp
// 辗转相除法
int  gcd3(int x,int y){
    int big = fmax(x,y);
    int small = fmin(x,y);
    int remainder = big % small;
    while(remainder){
        big = small;
        small = remainder;
        remainder = big % small;
    }
    return small;
}
```
------------

##4.辗转相减法（更相减损法）
###原理
`“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。” --《九章算术》`

###步骤
```cpp
1.任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
2.以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
```
###代码
```cpp
// 辗转相减法（更相减损法）【递归】
int  gcd4(int x,int y){
    int big = fmax(x,y);
    int small = fmin(x,y);
    int delta = big - small;
    if (delta == small)
         return delta;
    else
        return gcd4(big-small,small);
}
```
```cpp
// 辗转相减法（更相减损法）【非递归】
int gcd5(int x,int y){
  int big = fmax(x, y);
  int small = fmin(x, y);
  int divisor = 1;
  while (big % 2 == 0 && small % 2 == 0) {
    big >>= 1;
    small >>= 1;
    divisor <<= 1;
  }
  int delta;
  delta = big - small;
  while (delta != small) {
    big = fmax(delta, small);
    small = fmin(delta, small);
    delta = big - small;
  }
  divisor *= delta;
  return divisor;

}
```
------------
##5.Stein算法（大数）
##原理
```cpp
原理：gcd(ka,kb)=k*gcd(a,b)
设x，y为非0奇数，有以下结论：
	gcd(x,0)=x
	gcd(2x,2y)=2*gcd(x,y)
	gcd(2x,y)=gcd(x,y)
	gcd(x,2y)=gcd(x,y)
	gcd(x,y)=gcd(|x-y|,min(x,y))
```
###代码
```cpp
//Stein算法【非递归】
int gcd6(int a,int b){
  int divisor = 1;

while (a || b) {
    if(!a)
        return divisor*b;
    if(!b)
        return divisor*a;

if (a % 2 == 0 && b % 2 == 0) {
      a >>= 1;
      b >>= 1;
      divisor <<= 1;
    } else if (a % 2 == 0) {
      a >>= 1;
    } else if (b % 2 == 0) {
      b >>= 1;
    } else {
      int t=a;
      a = abs(a - b);
      b = fmin(t, b);
    }
  }

return divisor;
}
```
```cpp
//Stein算法【递归】
int gcd7(int a, int b) {
    if(!a)
        return b;
    if(!b)
        return a;
    if(!(a & 1) && !(b & 1))
        return gcd7(a >> 1, b >> 1) << 1;
    else if(!(a & 1))
        return gcd7(a >> 1, b);
    else if(!(b & 1))
        return gcd7(a, b >> 1);
    return gcd7(abs(a - b), min(a, b));
}

```
------------

#题解代码
```cpp
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;

int gcd1(int x,int y);//暴力穷举法
int gcd2(int x,int y);//短除法
int gcd3(int x,int y);//辗转相除法
int gcd4(int x,int y);//辗转相减法（更相减损法）【递归】
int gcd5(int x,int y);//辗转相减法（更相减损法）【非递归】
int gcd6(int x,int y);//Stein算法【非递归】
int gcd7(int a, int b);//Stein算法【递归】

int main()
{
   int x = 0, y = 0,gcd;
   cin>>x>>y;
   gcd = gcd1(x,y);
   //gcd = gcd2(x,y);
   //gcd = gcd3(x,y);
   //gcd = gcd4(x,y);
   //gcd = gcd5(x,y);
   //gcd = gcd6(x,y);
   //gcd = gcd7(x,y);
   cout<<gcd<<" "<<x*y/gcd<<endl;

}
//暴力穷举法
int gcd1(int x,int y){

int tmp = fmin(x,y); //把两个数的最小值赋给tmp
	while (1)
	{
		if (x % tmp == 0 && y % tmp == 0)
		{
			break;  
		}
		tmp--;  
	}
	return tmp;
}

// 短除法
int  gcd2(int x,int y){

int tmp = 1;
	for(int i = 2;i<=x&&i<=y;i++){
		while(x%i==0&&y%i==0){      //while 的用法是用来控制从最低的二开始判断的
			tmp = tmp*i;
			x /= i;
			y /= i;
		}
	}
    return tmp;
}

// 辗转相除法
int  gcd3(int x,int y){
    int big = fmax(x,y);
    int small = fmin(x,y);
    int remainder = big % small;
    while(remainder){
        big = small;
        small = remainder;
        remainder = big % small;
    }
    return small;
}

// 辗转相减法（更相减损法）【递归】
int  gcd4(int x,int y){
    int big = fmax(x,y);
    int small = fmin(x,y);
    int delta = big - small;
    if (delta == small)
         return delta;
    else
        return gcd4(big-small,small);
}

// 辗转相减法（更相减损法）【非递归】
int gcd5(int x,int y){
  int big = fmax(x, y);
  int small = fmin(x, y);
  int divisor = 1;
  while (big % 2 == 0 && small % 2 == 0) {
    big >>= 1;
    small >>= 1;
    divisor <<= 1;
  }
  int delta;
  delta = big - small;
  while (delta != small) {
    big = fmax(delta, small);
    small = fmin(delta, small);
    delta = big - small;
  }
  divisor *= delta;
  return divisor;

}

//Stein算法【非递归】
int gcd6(int a,int b){
  int divisor = 1;

while (a || b) {
    if(!a)
        return divisor*b;
    if(!b)
        return divisor*a;

return divisor;
}

//Stein算法【递归】
int gcd7(int a, int b) {
    if(!a)
        return b;
    if(!b)
        return a;
    if(!(a & 1) && !(b & 1))
        return gcd7(a >> 1, b >> 1) << 1;
    else if(!(a & 1))
        return gcd7(a >> 1, b);
    else if(!(b & 1))
        return gcd7(a, b >> 1);
    return gcd7(abs(a - b), min(a, b));
}

```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

分糖果（C++代码）

点我有惊喜！你懂得！

【原理、题解、代码】最大公约数与最小公倍数

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言训练-斐波纳契数列（C语言代码）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

【计算两点间的距离】（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

陶陶摘苹果2 （C语言代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言训练-计算：t=1-1/(2*2)-1/(3*3)-...-1/(m*m) （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

分糖果 （C++代码）

点我有惊喜！你懂得！

【原理、题解、代码】最大公约数与最小公倍数

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言训练-斐波纳契数列 （C语言代码）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

【计算两点间的距离】 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

陶陶摘苹果2 （C语言代码）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

分糖果（C++代码）

　　评论区

C语言训练-斐波纳契数列（C语言代码）

【计算两点间的距离】（C语言代码）