专栏文章

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

MMax_robot
B3736题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq99o5y
此快照首次捕获于
2025/12/04 01:03
3 个月前
此快照最后确认于
2025/12/04 01:03
3 个月前
查看原文
这里我们提供两种解决方案。

暴力枚举

我们注意到这道题的数据特别小，所以考虑暴力枚举。那么，怎么枚举？很简单，我们从 10610^6 枚举到 1，然后进行一些判断。
那么，为什么要从 10610^6 枚举到 1，而不是从 1 枚举到 10610^6 呢？注意到要求最大公因数，所以从大到小枚举是不错的选择。当然，如果从 1 开始枚举，那么代码永远只会输出 1。
然后来说一下判断条件。我们首先要判断 ii 是不是小于 x,y,zx,y,z。因为如果大于，就不能 mod 了。然后根据题目判断就行了。
如果还有什么不懂的就直接看代码吧。
CPP
#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)O(n)。

用最大公因数函数

如标题，C++ 里有一个求最大公因数的函数。这个函数就是__gcd(x,y)。前面是两个下划线。
还要注意一点，就是这个函数里面只能放相同类型的变量。
那么如何使用这个函数呢？我们可以先求出前两个数的最大公因数。然后求前两个数的最大公因数和最后一个数的最大公因数。
最后输出就好了。
如果还有什么不懂的就直接看代码吧。
CPP
#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;//结束程序
}
时间复杂度为对数级别。

结尾

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...