[信息与未来 2018] 最大公约数(Greatest Common Divisor of Three) 题解

思路分析

最大公约数满足结合律：$\gcd(x, y, z) = \gcd(\gcd(x, y), z)$。使用欧几里得算法（辗转相除法）调用两次 gcd 即可，时间复杂度 $O(\log(\max(x, y, z)))$。

参考代码

#include <iostream>
using namespace std;

int myGcd(int a, int b)
{
    while (b != 0)
    {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int x, y, z;
    if (!(cin >> x >> y >> z)) return 0;
    cout << myGcd(myGcd(x, y), z) << "\n";
    return 0;
}