【GESP】C++二级练习 luogu-B3736 [信息与未来 2018] 最大公约数

GESP二级练习，循环分支练习，难度★☆☆☆☆。

luogu-B3736 [信息与未来 2018] 最大公约数

题目要求

题目描述

输入三个正整数 $x,y,z$，求它们的最大公约数（Greatest Common Divisor）$g$：最大的正整数 $g ≥1$，满足 $x,y,z$ 都是 $g$ 的倍数，即 $(x \bmod g) = (y \bmod g) = (z \bmod g) = 0$。

输入格式

输入一行三个正整数 $x,y,z$。

输出格式

输出一行一个整数 $g$，表示 $x,y,z$ 的最大公约数。

输入 #1

12 34 56

输出 #1

2

输入 #2

28 70 28

输出 #2

14

数据规模

所有数据满足 $1 ≤ x,y,z ≤ 10^6$。

本题原始满分为 $15\text{pts}$。

题目分析

解题思路

1. 最大公约数不会超过三个数中的最小值，因此可以从最小值开始向下枚举，第一个能同时整除三个数的值即为答案。

2. 实现步骤：

   • 读入三个正整数 $x, y, z$。
   • 用 min(x, min(y, z)) 求出三者的最小值 $m$。
   • 从 $i = m$ 到 $i = 1$ 递减遍历，判断 x % i == 0 && y % i == 0 && z % i == 0。
   • 找到第一个满足条件的 $i$，即为最大公约数，break 退出循环。
   • 输出结果。

示例代码

#include <cmath>
#include <iostream>

using namespace std;
int main() {
    // 声明三个整数变量用于存储输入的数字
    int x, y, z;
    // 从标准输入读取三个数字
    cin >> x >> y >> z;
    // 找出三个数字中的最小值，因为最大公约数不会超过最小的数
    int m = min(x, min(y, z));
    // 初始化答案变量
    int ans = 0;
    // 从最小值开始向下遍历，找到第一个能同时整除三个数的数
    for (int i = m; i >= 1; i--) {
        // 判断i是否能同时整除x、y、z
        if (x % i == 0 && y % i == 0 && z % i == 0) {
            // 找到最大公约数，赋值给ans
            ans = i;
            // 找到后立即退出循环
            break;
        }
    }
    // 输出最大公约数
    cout << ans;
    // 程序正常结束
    return 0;
}