PTA-101b-数据结构（求两个正整数的最大公约数、求数组与整数乘积的最大值、将数组中元素反转存放、计算1 ~ n与1 ~ m每一项相互乘积的和）

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

分数 15

作者 陈越

单位 浙江大学

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

输入格式：

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

输出格式：

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

输入样例：

73472 48503

输出样例：

287

解析

#include <iostream>
using namespace std;
int main()
{
    int a , b;
    cin >> a >> b;
    int m =1;
    for  (int i = 1; m != 0; i++)
    {
        m = a % b;
        a = b;
        b = m;
    }
    cout << a << endl;
    return 0;
}

注意

辗转相除法

辗转相除法（欧几里得算法）

辗转相除法（又称欧几里得算法）是求两个正整数最大公约数（GCD，Greatest Common Divisor） 的经典高效算法，由古希腊数学家欧几里得在《几何原本》中提出。它的核心是通过 “不断用较小数和两数余数替换原数”，直到余数为 0，此时的除数即为最大公约数。

一、核心定义与原理

1. 最大公约数（GCD）

两个正整数的最大公约数，是指能同时整除这两个数的最大正整数。例如：

• 12 和 18 的公约数有 1、2、3、6，其中最大公约数是 6，记为 gcd(12,18)=6。

2. 辗转相除法核心原理

对于任意两个正整数 a 和 b（约定 a ≥ b），满足以下递推关系：gcd(a, b) = gcd(b, a mod b)

• 其中 a mod b 表示 “a 除以 b 的余数”（余数范围：0 ≤ 余数 < b）。
• 终止条件：当 b = 0 时，gcd(a, 0) = a（因为任何数都能整除 0，此时 a 就是最大公约数）。

二、计算步骤（带示例）

以计算 gcd(48, 18) 为例，步骤如下：

步骤	被除数（a）	除数（b）	计算：a ÷ b 的商和余数	递推关系	结果判断
1	48	18	48 ÷ 18 = 2 余 12	gcd(48,18) = gcd(18,12)	余数≠0，继续
2	18	12	18 ÷ 12 = 1 余 6	gcd(18,12) = gcd(12,6)	余数≠0，继续
3	12	6	12 ÷ 6 = 2 余 0	gcd(12,6) = gcd(6,0)	余数 = 0，终止
4	6	0	——	gcd(6,0) = 6	最终 GCD=6

另一个示例：计算 gcd(21, 15)

1. gcd(21,15) = gcd(15, 21 mod 15) = gcd(15,6)
2. gcd(15,6) = gcd(6, 15 mod 6) = gcd(6,3)
3. gcd(6,3) = gcd(3, 6 mod 3) = gcd(3,0)
4. gcd(3,0) = 3，最终结果：gcd(21,15)=3

三、主要用途

1. 求两个数的最大公约数（核心用途）

直接应用算法即可，如上文示例。需注意：

• 若 a < b，算法会自动调整顺序（例如 gcd(18,48) 会先转为 gcd(48,18)，因为 18 mod 48 = 18）。
• 若其中一个数为 0，另一个数就是 GCD（例如 gcd(5,0)=5，gcd(0,0) 无意义）。

2. 求两个数的最小公倍数（LCM）

最小公倍数（LCM，Least Common Multiple）是能同时被两个数整除的最小正整数，与 GCD 的关系为：LCM(a, b) = (a × b) ÷ GCD(a, b)

• 示例：求

  LCM(48,18)

  已知

  gcd(48,18)=6

  ，则

  LCM(48,18) = (48×18) ÷ 6 = 144

3. 扩展：求多个数的 GCD/LCM

• 求多个数的 GCD：依次计算，例如

  gcd(a,b,c) = gcd(gcd(a,b), c)

  示例：

  gcd(12,18,24) = gcd(gcd(12,18),24) = gcd(6,24) = 6

  。

• 求多个数的 LCM：同理依次计算，例如 LCM(a,b,c) = LCM(LCM(a,b), c)。

四、算法效率

辗转相除法是高效算法，时间复杂度为 O(log(min(a,b)))（对数级别）。

• 原因：每次迭代中，a mod b 的结果至少是 a 的一半（例如 a=48，b=18，余数 12＜48/2；a=18，b=12，余数 6＜18/2），因此问题规模会快速缩小。
• 对比 “枚举法”（从较小数向下枚举公约数）：对于大数（如 10⁶级别），辗转相除法的效率优势极其明显。

五、代码实现（以 Java 为例）

1. 递归实现（直观体现递推关系）

java运行

public class GCDCalculator {
    // 递归计算gcd(a,b)
    public static int gcd(int a, int b) {
        // 终止条件：b=0时，返回a
        if (b == 0) {
            return a;
        }
        // 递推：gcd(a,b) = gcd(b, a%b)
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        int a = 48;
        int b = 18;
        System.out.println("gcd(" + a + "," + b + ") = " + gcd(a, b)); // 输出6
        System.out.println("lcm(" + a + "," + b + ") = " + (a * b) / gcd(a, b)); // 输出144
    }
}

2. 迭代实现（避免递归栈溢出，适合大数）

java运行

public static int gcdIterative(int a, int b) {
    // 循环直到b=0
    while (b != 0) {
        int temp = b; // 保存当前b
        b = a % b;   // 更新b为a%b
        a = temp;    // 更新a为原b
    }
    return a; // 最终a即为GCD
}

六、常见误区

1. 余数必须非负：a mod b 的结果一定是 0 ≤ 余数 < b，例如 18 mod 48 = 18，5 mod 3 = 2。
2. 顺序不影响结果：gcd(a,b) = gcd(b,a)，算法会自动调整被除数和除数的顺序。
3. 处理负数：若输入包含负数，可先取绝对值（因为 gcd(-48,18) = gcd(48,18)=6）。

通过以上内容，可全面理解辗转相除法的原理、应用及实现，它不仅是数学中的基础算法，也是编程中处理 “整除问题” 的核心工具（如分数化简、密码学、数据加密等场景）。

算法1-1~2 求数组与整数乘积的最大值

分数 15

作者 陈越

单位 浙江大学

给定 n 个正整数和另一个整数因子 m。请编写程序，将 n 个整数存在数组中，逐一乘以 m，并求所有乘积中的最大值。
注：虽然题目要求将输入的 n 个整数存储在数组中，再进行解决，但完全不用数组存储也是可以得到解的。

输入格式：

输入第一行给出一对正整数 n（≤104）和 m（≤100）。第二行给出 n 个 [1,103] 区间内的正整数。同行数字间以空格分隔。

输出格式：

在一行中输出题面中要求的最大值。

输入样例：

5 3
123 45 678 9 10

输出样例：

2034

解析

# include <iostream>
using namespace std;
int main()
{
    int a , b;
    cin >>a >>b;
    int max = 0;
    int c;
    for ( int i = 0 ; i < a ; i++ )
    {
        int d;
        cin >>d;
        c = d;
        if  (c * b > max)
            max = c * b;
    }
    cout << max;
    return 0;
}

注意

一边循环一边刷新max

算法1-3~4 将数组中元素反转存放

分数 15

作者 陈越

单位 浙江大学

给定 n 个 int 型范围内的整数。请编写程序，将 n 个整数存在数组中，再将这些数组元素反转存放，最后顺序输出反转后数组中的元素。
注：虽然不需要改变数组中元素的位置，也可以按反转的顺序输出，但建议练习者尝试反转数组元素的算法。

输入格式：

输入第一行给出正整数 n（≤104）。第二行给出 n 个 int 型范围内的整数。同行数字间以空格分隔。

输出格式：

在一行中输出反转输入顺序后的结果，每个数字后跟 1 个空格。

输入样例：

5
1 2 3 4 5

输出样例：

5 4 3 2 1 

解析

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int a[10000];
    for ( int i = 0 ; i < n ; i++ )
        cin >> a[i];
    for ( int j = 0 ; j < n/2 ; j++ )
    {
        int temp;
        temp = a[n - j - 1];
        a[n - j - 1] = a[j];
        a[j] = temp;
    }
    for ( int k = 0 ; k < n ; k++ )
        cout << a[k] << " ";
    return 0;
}

算法1-5 计算1~n平方的和加上1~n的和

分数 10

作者 陈越

单位 浙江大学

给定正整数 n，请编写程序，求 (1+2+⋯+n2)+(1+2+⋯+n) 的值。

输入格式：

输入在一行中给出正整数 n（≤100）。

输出格式：

在一行中输出题面中要求的值。

输入样例：

5

输出样例：

340

解析

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    long long int sum = n * (n + 1) / 2;
    long long int sum2 = n * n * (n * n + 1) / 2;
    
    long long int sum3 = sum2 + sum;
    cout << sum3 << endl;
    return 0;
}

注意

使用 long long 类型避免整数溢出（当 n 较大时，n² 可能超过 int 范围）。

算法1-6 计算1 ~ n与1 ~ m每一项相互乘积的和

分数 10

作者 陈越

单位 浙江大学

给定两个正整数 n 和 m，请编写程序，求 1~n 与 1~m 每一项相互乘积的和。

输入格式：

输入在一行中给出两个正整数 n 和 m，均不超过 100，其间以空格分隔。

输出格式：

在一行中输出题面中要求的值。

输入样例：

5 3

输出样例：

90

解析

#include <iostream>
using namespace std;
int main()
{
    int n , m;
    cin >> n >> m;
    int i , j;
    int sum1 = 0 , sum2 = 0;
    for (i = 1; i <= n; i++)
    {
        sum1 = sum1 + i;
    }
    for (j = 1; j <= m; j++)
    {
        sum2 = sum2 + j;
    }
    long long int sum3 = sum1 * sum2;
    cout << sum3;
    return 0;

}

注意

问题分析

题目中的 “每一项相互乘积的和” 指的是：((1×1) + (1×2) + … + (1×m) + (2×1) + (2×2) + … + (2×m) + … + (n×1) + (n×2) + … + (n×m))

通过数学化简，这个总和可以表示为 “1~n 的和” 与 “1~m 的和” 的乘积（利用乘法分配律）：(\left( \sum_{i=1}^n i \right) \times \left( \sum_{j=1}^m j \right))

你的代码错误地计算了 “1~n 的阶乘” 和 “1~m 的阶乘” 的和，与题目要求完全不符。

修正思路

1. 计算 1~n 的和：公式为 $(sum\_n = \frac{n(n+1)}{2})$
2. 计算 1~m 的和：公式为 $(sum\_m = \frac{m(m+1)}{2})$
3. 总和为两者的乘积：$$(total = sum_n \times sum_m)$$