PTA 算法0-0 求两个正整数的最大公约数

算法0-0 求两个正整数的最大公约数

分数 15

作者 陈越

单位 浙江大学

请编写程序，求两个正整数的最大公约数。

输入格式：

输入在一行中给出一对正整数 0<x,y≤106，数字间以空格分隔。

输出格式：

在一行中输出 x 和 y 的最大公约数。

输入样例：

1
73472 48503

输出样例：

1
287

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

// 欧几里得算法（辗转相除法）求最大公约数
int gcd(int m, int n) {
    // 当b为0时，a就是最大公约数
    while (n != 0) {
        int temp = m % n;  // 计算a除以b的余数
        m = n;             // 把b的值赋给a
        n = temp;          // 把余数赋给b
    }
    return m;
}

int main() {
    int x, y;
    cin >> x >> y;

    // 输出最大公约数
    cout << gcd(x, y) << endl;

    return 0;
}

1.讲解欧几里得算法过程

循环次数 m 的值 n 的值 计算 temp = m % n 循环条件 (n≠0)
初始 16 24 - 24≠0（进入循环）
1 16 24 16 % 24 = 16 16≠0（继续循环）
2 24 16 24 % 16 = 8 8≠0（继续循环）
3 16 8 16 % 8 = 0 0=0（退出循环）

2.时间复杂度分析：O (log min (m,n))

欧几里得算法的时间复杂度与输入数字的位数成正比，证明思路如下：

  1. 每次迭代中，m % n的结果一定小于n/2（这是由取余运算的性质决定的）
  2. 这意味着每两次迭代后，数值至少会减少一半
  3. 对于最小值为k的两个数，需要的迭代次数不会超过log₂k

以 16 和 24 为例，最小值是 16，log₂16=4，而实际只需要 3 次迭代就完成了计算，符合复杂度范围。

3.增加最小公倍数计算

最大公约数（gcd）和最小公倍数（lcm）有一个重要关系：

1
lcm(a,b) = |a×b| / gcd(a,b)
1
2
3
4
// 利用gcd求最小公倍数
int lcm(int a, int b) {
    return a * b / gcd(a, b);  // 基于公式：lcm(a,b) = a*b/gcd(a,b)
}