题解 | #最大公约数#

简单数学题，辗转相除法求最大公约数：

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }  // 递归形式
// int gcd(int a, int b) { while (b) { int t = a % b; a = b; b = t; } return a; } // 迭代形式

void solve()
{
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    int t;
    // cin >> t;
    t = 1;
    while (t--)
        solve();
    return 0;
}

如果你不想自己定义 gcd 函数，也可以使用 <algorithm> 头文件中的 __gcd 函数。

除了最大公约数，还有最小公倍数，可以使用 a * b / gcd(a, b) 求得。