[已解决]最大公约数(2147483647)

player-none

输入两个正整数a,b，求其最大公约数（$1<=a , b<=2147483647$）。

崩溃了，怎么压缩时间啊

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int main(){
   
4.     int a,b;
   
5.     cin>>a>>b;
   
6.     if(a<b){
   
7.         swap(a,b);
   
8.     }
   
9.     if(a%b==0){
   
10.         cout<<b;
    
11.     }else{
    
12.             int zuida;
    
13.             for(int i=1;i<=b;++i){
    
14.                     if(a%i==0&&b%i==0){
    
15.                             zuida=i;
    
16.                     }
    
17.                 }
    
18.                 cout<<zuida;
    
19.         }
    
20.     return 0;
    
21. }

复制代码

最佳答案

月排行榜 / 总排行榜

FishC

2025-3-15 12:13:11

看起来你的问题是关于求两个正整数的最大公约数（GCD）。你可以使用欧几里得算法（辗转相除法）来计算 GCD，以下是 C++ 代码示例：

1. #include <iostream>
   
2. 
   
3. int gcd(int a, int b) {
   
4.     while (b != 0) {
   
5.         int temp = b;
   
6.         b = a % b;
   
7.         a = temp;
   
8.     }
   
9.     return a;
   
10. }
    
11. 
    
12. int main() {
    
13.     int a, b;
    
14.     std::cin >> a >> b;
    
15.     std::cout << gcd(a, b) << std::endl;
    
16.     return 0;
    
17. }

复制代码

这个算法的核心思想是：  
- 如果 `b` 不为 0，则 `gcd(a, b) = gcd(b, a % b)`，不断递归或迭代，直到 `b == 0`，此时 `a` 就是最大公约数。

如果你有更具体的问题，欢迎继续提问！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

看起来你的问题是关于求两个正整数的最大公约数（GCD）。你可以使用欧几里得算法（辗转相除法）来计算 GCD，以下是 C++ 代码示例：

1. #include <iostream>
   
2. 
   
3. int gcd(int a, int b) {
   
4.     while (b != 0) {
   
5.         int temp = b;
   
6.         b = a % b;
   
7.         a = temp;
   
8.     }
   
9.     return a;
   
10. }
    
11. 
    
12. int main() {
    
13.     int a, b;
    
14.     std::cin >> a >> b;
    
15.     std::cout << gcd(a, b) << std::endl;
    
16.     return 0;
    
17. }

复制代码

这个算法的核心思想是：  
- 如果 `b` 不为 0，则 `gcd(a, b) = gcd(b, a % b)`，不断递归或迭代，直到 `b == 0`，此时 `a` 就是最大公约数。

如果你有更具体的问题，欢迎继续提问！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。