[已解决]最大公约数与最小公倍数问题

player-none

输入两个正整数x0,y0($2<=x0<100000,2<=y0<=100000$),求出满足下列条件的P,Q的个数
条件:
1.P,Q是正整数
2.要求P,Q以x0为最大公约数,以y0为最小公倍数.
试求:满足条件的所有可能的两个正整数的个数.
输入描述
输入二个正整数x0,y0(2<=x0<100000,2<=y0<=100000)
输出描述
输出满足条件的P,Q的个数。
样例1
输入
3 60
输出
4
说明(不用输出)此时的PQ分别为:
3        60
15        12
12        15
60        3
所以:满足条件的所有可能的两个正整数的个数共4种.

我的代码

#include <iostream>
using namespace std;
int gcd(int a, int b) {
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
int lcm(int a, int b){
    return (a / gcd(a, b)) * b;
}
int main()
{
         int x,y,cnt=0;
         cin>>x>>y;
         for(int p=x;p<=y;++p){
             for(int q=x;q<=y;++q){
                 if(gcd(p,q)==x&&lcm(p,q)==y){
               //  if(p*q==x*y){
                     cnt++;
                 }
             }
         }
         cout<<cnt<<endl;
    return 0;
}

我已问过 AI，他给出的答案如下：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// 辗转相除法求最大公约数
int gcd(int a, int b) {
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 计算y0/x0的所有因子
vector<int> getFactors(int n) {
    vector<int> factors;
    for (int i = 1; i <= sqrt(n); ++i) {
        if (n % i == 0) {
            factors.push_back(i);
            if (i != n / i) {
                factors.push_back(n / i);
            }
        }
    }
    return factors;
}

int main() {
    int x0, y0;
    cin >> x0 >> y0;
    
    if (y0 % x0 != 0) {
        cout << 0 << endl; // 如果y0不是x0的倍数，则不可能满足条件
        return 0;
    }
    
    int n = y0 / x0;
    vector<int> factors = getFactors(n);
    int count = 0;
    
    for (int k1 : factors) {
        int k2 = n / k1;
        if (gcd(k1, k2) == 1) {
            count += 2; // (k1*x0, k2*x0) 和 (k2*x0, k1*x0) 是两对解，但算一对，所以最后结果乘以2
        }
    }
    
    // 如果n是一个完全平方数，则存在一对(sqrt(n)*x0, sqrt(n)*x0)，这种情况只应计算一次
    if (sqrt(n) == static_cast<int>(sqrt(n))) {
        count -= 1;
    }
    
    cout << count << endl;
    return 0;
}

似乎并不正确。

最佳答案

月排行榜 / 总排行榜

sfqxx

2025-3-16 11:26:55

试试这个？

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// 辗转相除法求最大公约数
int gcd(int a, int b) {
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 计算n的所有因子
vector<int> getFactors(int n) {
    vector<int> factors;
    for (int i = 1; i <= sqrt(n); ++i) {
        if (n % i == 0) {
            factors.push_back(i);
            if (i != n / i) {
                factors.push_back(n / i);
            }
        }
    }
    return factors;
}

int main() {
    int x0, y0;
    cin >> x0 >> y0;
    
    if (y0 % x0 != 0) {
        cout << 0 << endl; // 如果y0不是x0的倍数，则不可能满足条件
        return 0;
    }
    
    int n = y0 / x0;
    vector<int> factors = getFactors(n);
    int count = 0;
    
    for (int a : factors) {
        int b = n / a;
        if (gcd(a, b) == 1) {
            count++;
        }
    }
    
    cout << count << endl;
    return 0;
}

跳转到最佳答案楼层

FishC

最大公约数与最小公倍数计算  

要计算两个正整数 x0 和 y0 的最大公约数（GCD）和最小公倍数（LCM），可以使用欧几里得算法（辗转相除法）来求 GCD，然后利用公式计算 LCM：

公式：  
- 最大公约数（GCD）：使用欧几里得算法  
- 最小公倍数（LCM）：LCM(x0, y0) = (x0 * y0) / GCD(x0, y0)  

Python 代码实现：  

  
def gcd(a, b):  
    while b:  
        a, b = b, a % b  
    return a  

def lcm(a, b):  
    return (a * b) // gcd(a, b)  

x0 = int(input("请输入第一个正整数: "))  
y0 = int(input("请输入第二个正整数: "))  

print("最大公约数:", gcd(x0, y0))  
print("最小公倍数:", lcm(x0, y0))  

这个代码会让用户输入两个正整数，然后计算并输出它们的最大公约数和最小公倍数。

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

sfqxx

试试这个？

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// 辗转相除法求最大公约数
int gcd(int a, int b) {
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 计算n的所有因子
vector<int> getFactors(int n) {
    vector<int> factors;
    for (int i = 1; i <= sqrt(n); ++i) {
        if (n % i == 0) {
            factors.push_back(i);
            if (i != n / i) {
                factors.push_back(n / i);
            }
        }
    }
    return factors;
}

int main() {
    int x0, y0;
    cin >> x0 >> y0;
    
    if (y0 % x0 != 0) {
        cout << 0 << endl; // 如果y0不是x0的倍数，则不可能满足条件
        return 0;
    }
    
    int n = y0 / x0;
    vector<int> factors = getFactors(n);
    int count = 0;
    
    for (int a : factors) {
        int b = n / a;
        if (gcd(a, b) == 1) {
            count++;
        }
    }
    
    cout << count << endl;
    return 0;
}