欧几里得算法-知识总结 概念 欧几里得辗转相除法，通常简称为欧几里得算法或辗转相除法，是一种用来求两个正整数最大公约数（GCD）的古老且有效的算法。该算法基于一个基本的数学原理：两个数的最大公约数不变，即使一个数被另一个数的余数替换之后。
算法原理
算法描述
欧几里得算法可以描述为以下步骤：
输入两个正整数 a和b，且a≥b。如果a
代码模版
1#include<iostream>
2using namespace std;
3
4int gcd(int a, int b) {
5 if (b == 0) {
6 return a;
7 }
8 return gcd(b, a % b);
9}
10
11int main() {
12 int n = 0;
13 int m = 0;
14 while (true) {
15 cin >> n >> m;
16 cout << gcd(n, m) << endl;
17 }
18 return 0;
19}例子 假设需要计算 252 和 105 的最大公约数： 第一步：计算252÷105=2，余数42，即252 mod 105=42。 第二步：计算105÷42=2，余数21，即105 mod 42=21。 第三步：计算42÷21=2，余数0，即42 mod 21=0。 最大公约数是最后的非零余数，即21。
效率 欧几里得算法是高效的，特别适用于大数的最大公约数计算。它的时间复杂度大约是 O(log(min(a,b)))，这使得即使对于非常大的数字，算法也能迅速收敛到结果。
总结作业非常重要，请务必认真完成✔️
考试只有一次提交机会，请务必本地检查正确后再提交❇️