有A、B、C三个整数,请问整数1~N以内是A、B、C中某两数的公约数的数有几个?
时间: 2023-10-03 17:07:19 浏览: 46
我们可以枚举1~N以内的每个数,然后判断它是不是A、B、C中某两数的公约数。具体地,对于每个数x,我们可以遍历A、B、C三个数,对于任意两个数i和j(i≠j),如果它们的最大公约数是x,则说明x是它们的公约数。最后我们统计一下共有多少个数x满足条件即可。
代码如下:
```
#include <iostream>
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
int A, B, C, N;
cin >> A >> B >> C >> N;
int ans = 0;
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) {
if (gcd(i, j) == A || gcd(i, j) == B || gcd(i, j) == C) {
ans++;
}
}
}
cout << ans << endl;
return 0;
}
```
这个算法的时间复杂度是O(N^2),对于N比较大的情况可能会超时。我们可以稍微优化一下,注意到如果i和j的最大公约数是x,那么i*x和j*x的最大公约数也是x,因此我们可以只枚举i和j的最大公约数,然后再统计它们的倍数即可。这样做可以将时间复杂度降为O(NlogN)。
优化后的代码如下:
```
#include <iostream>
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
int A, B, C, N;
cin >> A >> B >> C >> N;
int ans = 0;
for (int i = 1; i <= N; i++) {
if (gcd(i, A) == i || gcd(i, B) == i || gcd(i, C) == i) {
for (int j = 1; i * j <= N; j++) {
ans++;
}
}
}
cout << ans << endl;
return 0;
}
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)