P22164题解

• . 方法一：就用题目指定的方法 “更损相减法” ，那我们写一个递归函数fun()，重复 更损相减 这一过程，直至求出解；

#include<bits/stdc++.h>
using namespace std;

void fun(int m,int n){
	if(m<n) swap(m,n);//判断大小 m必须小于n,否则差就是负数
	if(m==n) cout<<n;//求出解
	else fun(m-n,n);//更损相减
}

int main(){
	int m,n;
	cin>>m>>n;
	fun(m,n);//调用函数
	return 0;//养成好习惯
}

• 方法二：“叫你用更损相减，你就用，这么老实啊。”，其实更损相减法有一个很大缺陷：“运行次数太多了”，如果是两个很大的质数那么递归将执行很多次。 ======================================================================================================这里我们引入一个简便的方法：“欧几里得算法”，也叫辗转相除。你可以理解为反复分割一个长方形直至分割出一个正方形。

using namespace std;

void fun(int m,int n){
	if(m%n==0) cout<<n;//求出解
	else fun(n,m%n);//辗转相除
}

int main(){
	int m,n;
	cin>>m>>n;
	fun(m,n);//调用函数
	return 0;//养成好习惯
}
```好了完结撒花QWQ