普通欧几里得

普通欧几里得算法经常用于求最大公约数，用普通欧几里得求最大公约数的做法我们叫它辗转相除法
普通欧几里得算法的核心算式是：gcd(a,b) = gcd(b,a % b)，其中a > b > 0
下面解释它的原理:
设正整数d为a,b的最大公约数（a > b > 0）
则a = k1 * d,b = k2 * d;
不妨设a = k3 * b + K * d（K * d < b）
由此可以得到a % b = a - k3 * b = K * d
所以gcd(a,b) = gcd(b,a % b) = d;
求这个最大公约数的过程我们可以用递归来实现
代码如下

#include <bits/stdc++.h>
using namespace std;int gcd(int a,int b){if (a % b == 0) return b;return gcd(b,a % b);
}int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int a,b;cin >> a >> b;cout << gcd(a,b);return 0;
}

当然我们的c++也有最大公约数函数__gcd(a,b)
上面的代码可以简化成这样

#include <bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int a,b;cin >> a >> b;cout << __gcd(a,b);return 0;
}

一般都是直接调用c++自带的gcd函数，c++自带的gcd函数不管是在时间上还是在空间上都比手写的gcd更优其实也是因为我懒