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

player-none

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

崩溃了，怎么压缩时间啊

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    if(a<b){
        swap(a,b);
    }
    if(a%b==0){
        cout<<b;
    }else{
            int zuida;
            for(int i=1;i<=b;++i){
                    if(a%i==0&&b%i==0){
                            zuida=i;
                    }
                }
                cout<<zuida;
        }
    return 0;
}

最佳答案

月排行榜 / 总排行榜

FishC

2025-3-15 12:13:11

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

#include <iostream>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int a, b;
    std::cin >> a >> b;
    std::cout << gcd(a, b) << std::endl;
    return 0;
}

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

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

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

跳转到最佳答案楼层

FishC

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

#include <iostream>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int a, b;
    std::cin >> a >> b;
    std::cout << gcd(a, b) << std::endl;
    return 0;
}

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

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

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