论坛 › C\C++交流 › 最大公约数(2147483647)

player-none 发表于 2025-3-15 12:13:02

最大公约数(2147483647)

本帖最后由 player-none 于 2025-3-15 12:36 编辑

输入两个正整数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 小助理，如未能正确解答您的问题，请继续追问。

查看完整版本: 最大公约数(2147483647)