【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. 首先，我们需要理解题目的核心要求：
   • 输入三个正整数 x, y, z
   • 求这三个数的最大公约数
   • 最大公约数定义：能同时整除这三个数的最大正整数
2. 解题思路：
   • 基本方法：
     • 从三个数中的最小值开始向下遍历
     • 找到第一个能同时整除三个数的数即为最大公约数
   • 实现步骤：
     • 获取输入的三个数
     • 找出三个数中的最小值
     • 从最小值开始递减遍历
     • 判断当前数是否能同时整除三个输入数
   • 优化考虑：
     • 一旦找到符合条件的数就可以停止遍历
     • 最大公约数一定是正整数
     • 最大公约数不会超过输入数字中的最小值
   • 时间复杂度：
     • O(min(x,y,z))，最坏情况下需要遍历到1
   • 特殊情况：
     • 由题目限制条件可知，输入的数都是正整数，不需要考虑负数和零的情况

---

示例代码

#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;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。