B3736 题解

· · 题解

思路分析

对于求 \gcd(a,b,c)，我们可以先求出 k=\gcd(a,b)，结果即为 \gcd(k,c)。

接下来介绍三种求最大公约数的方法。

辗转相除法

这里不带证明的给出：

\gcd(a,b) = \begin{cases} a &b=0 \cr \gcd(b,a\mod b) &b\not=0 \end{cases}

根据递归式一路递归即可。

对于没有构造的数据，这种方法的时间复杂度基本是 \Theta(1)，但是最坏情况下的时间复杂度为 \mathcal O(\log\max\{a,b\}) 的。

更相减损法

对于一般的数据类型，辗转相除法的速度是比较快的，但是对于自己手写的高精度，取模运算会十分的慢，导致辗转相除法的效率大为降低。

所以我们可以用更相减损法来解决问题。但是需要注意这样的话运算次数会增加许多。

同样不带证明给出：

\gcd(a,b)=\begin{cases} a&a=b\\ \gcd(a-b,b)&a>b\\ \gcd(b-a,a)&a<b \end{cases}

STL 大法

在 <algorithm> 中，定义有一个函数 std::__gcd(a,b)，可以直接求出 \gcd(a,b)！

std::__gcd(a,b) 底层的实现应该是辗转相除法，所以时间复杂度是 \mathcal O(\log\max\{a,b\})。

代码演示

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int x, y, z;
    cin >> x >> y >> z;
    cout << __gcd(__gcd(x, y), z) << endl;
    return 0;
}