B3736 [信息与未来 2018] 最大公约数 题解

· · 题解

这里我们提供两种解决方案。

暴力枚举

我们注意到这道题的数据特别小，所以考虑暴力枚举。那么，怎么枚举？很简单，我们从 10^6 枚举到 1，然后进行一些判断。

那么，为什么要从 10^6 枚举到 1，而不是从 1 枚举到 10^6 呢？注意到要求最大公因数，所以从大到小枚举是不错的选择。当然，如果从 1 开始枚举，那么代码永远只会输出 1。

然后来说一下判断条件。我们首先要判断 i 是不是小于 x,y,z。因为如果大于，就不能 mod 了。然后根据题目判断就行了。

如果还有什么不懂的就直接看代码吧。

#include<bits/stdc++.h>//万能头文件
using namespace std;
long long x, y, z;
int main(){
    cin>>x>>y>>z;
    for(int i=1e6;i>=1;i--){//从 1e6 枚举到 1
        if(i>x && i>y && i>z) continue;//如果 i 大于 x,y,z,那么一定就不能 mod 了，所以 continue 掉
        else if(x%i==0 && y%i==0 && z%i==0){//如果符合条件
            cout<<i<<endl;//输出 i 
            return 0;//结束程序
        }
    }
    return 0;//结束程序
}

时间复杂度为 O(n)。

用最大公因数函数

如标题，C++ 里有一个求最大公因数的函数。这个函数就是__gcd(x,y)。前面是两个下划线。

还要注意一点，就是这个函数里面只能放相同类型的变量。

那么如何使用这个函数呢？我们可以先求出前两个数的最大公因数。然后求前两个数的最大公因数和最后一个数的最大公因数。

最后输出就好了。

如果还有什么不懂的就直接看代码吧。

#include<bits/stdc++.h>//万能头文件
using namespace std;
int x, y, z;
int main(){
    cin>>x>>y>>z;
    int cd=__gcd(x,y);//求前 x 和 y 的最大公因数，并存入一个叫 cd 的变量
    int gcd=__gcd(cd,z);//求 cd 和 z 的最大公因数
    cout<<gcd<<endl;//输出
    //这里再补充一下吧，就是__gcd函数里面只能放相同类型的变量，比如我放两个 int 或两个 long long
    return 0;//结束程序
}

时间复杂度为对数级别。

结尾

好了，两种方法都讲完了，在时间复杂度上显然第二种最优。但是第一种的代码更好写。所以两种思路都要看一下。这里建议大家用第二种方法，因为如果数据很大的话暴力是过不了的。

如果有什么写的不好的就私信我，我会第一时间改正。