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

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种.

我的代码

1. #include <iostream>
   
2. using namespace std;
   
3. int gcd(int a, int b) {
   
4.     while (b) {
   
5.         int temp = b;
   
6.         b = a % b;
   
7.         a = temp;
   
8.     }
   
9.     return a;
   
10. }
    
11. int lcm(int a, int b){
    
12.     return (a / gcd(a, b)) * b;
    
13. }
    
14. int main()
    
15. {
    
16.         int x,y,cnt=0;
    
17.         cin>>x>>y;
    
18.         for(int p=x;p<=y;++p){
    
19.             for(int q=x;q<=y;++q){
    
20.                 if(gcd(p,q)==x&&lcm(p,q)==y){
    
21.               //  if(p*q==x*y){
    
22.                     cnt++;
    
23.                 }
    
24.             }
    
25.         }
    
26.         cout<<cnt<<endl;
    
27.     return 0;
    
28. }

复制代码

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

1. #include <iostream>
   
2. #include <vector>
   
3. #include <cmath>
   
4. using namespace std;
   
5. 
   
6. // 辗转相除法求最大公约数
   
7. int gcd(int a, int b) {
   
8.     while (b) {
   
9.         int temp = b;
   
10.         b = a % b;
    
11.         a = temp;
    
12.     }
    
13.     return a;
    
14. }
    
15. 
    
16. // 计算y0/x0的所有因子
    
17. vector<int> getFactors(int n) {
    
18.     vector<int> factors;
    
19.     for (int i = 1; i <= sqrt(n); ++i) {
    
20.         if (n % i == 0) {
    
21.             factors.push_back(i);
    
22.             if (i != n / i) {
    
23.                 factors.push_back(n / i);
    
24.             }
    
25.         }
    
26.     }
    
27.     return factors;
    
28. }
    
29. 
    
30. int main() {
    
31.     int x0, y0;
    
32.     cin >> x0 >> y0;
    
33.    
    
34.     if (y0 % x0 != 0) {
    
35.         cout << 0 << endl; // 如果y0不是x0的倍数，则不可能满足条件
    
36.         return 0;
    
37.     }
    
38.    
    
39.     int n = y0 / x0;
    
40.     vector<int> factors = getFactors(n);
    
41.     int count = 0;
    
42.    
    
43.     for (int k1 : factors) {
    
44.         int k2 = n / k1;
    
45.         if (gcd(k1, k2) == 1) {
    
46.             count += 2; // (k1*x0, k2*x0) 和 (k2*x0, k1*x0) 是两对解，但算一对，所以最后结果乘以2
    
47.         }
    
48.     }
    
49.    
    
50.     // 如果n是一个完全平方数，则存在一对(sqrt(n)*x0, sqrt(n)*x0)，这种情况只应计算一次
    
51.     if (sqrt(n) == static_cast<int>(sqrt(n))) {
    
52.         count -= 1;
    
53.     }
    
54.    
    
55.     cout << count << endl;
    
56.     return 0;
    
57. }
    

复制代码

似乎并不正确。

最佳答案

月排行榜 / 总排行榜

sfqxx

2025-3-16 11:26:55

试试这个？

1. #include <iostream>
   
2. #include <vector>
   
3. #include <cmath>
   
4. using namespace std;
   
5. 
   
6. // 辗转相除法求最大公约数
   
7. int gcd(int a, int b) {
   
8.     while (b) {
   
9.         int temp = b;
   
10.         b = a % b;
    
11.         a = temp;
    
12.     }
    
13.     return a;
    
14. }
    
15. 
    
16. // 计算n的所有因子
    
17. vector<int> getFactors(int n) {
    
18.     vector<int> factors;
    
19.     for (int i = 1; i <= sqrt(n); ++i) {
    
20.         if (n % i == 0) {
    
21.             factors.push_back(i);
    
22.             if (i != n / i) {
    
23.                 factors.push_back(n / i);
    
24.             }
    
25.         }
    
26.     }
    
27.     return factors;
    
28. }
    
29. 
    
30. int main() {
    
31.     int x0, y0;
    
32.     cin >> x0 >> y0;
    
33.    
    
34.     if (y0 % x0 != 0) {
    
35.         cout << 0 << endl; // 如果y0不是x0的倍数，则不可能满足条件
    
36.         return 0;
    
37.     }
    
38.    
    
39.     int n = y0 / x0;
    
40.     vector<int> factors = getFactors(n);
    
41.     int count = 0;
    
42.    
    
43.     for (int a : factors) {
    
44.         int b = n / a;
    
45.         if (gcd(a, b) == 1) {
    
46.             count++;
    
47.         }
    
48.     }
    
49.    
    
50.     cout << count << endl;
    
51.     return 0;
    
52. }

复制代码

跳转到最佳答案楼层

FishC

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

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

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

Python 代码实现：  

1.   
   
2. def gcd(a, b):  
   
3.     while b:  
   
4.         a, b = b, a % b  
   
5.     return a  
   
6. 
   
7. def lcm(a, b):  
   
8.     return (a * b) // gcd(a, b)  
   
9. 
   
10. x0 = int(input("请输入第一个正整数: "))  
    
11. y0 = int(input("请输入第二个正整数: "))  
    
12. 
    
13. print("最大公约数:", gcd(x0, y0))  
    
14. print("最小公倍数:", lcm(x0, y0))  
    

复制代码

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

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

sfqxx

试试这个？

1. #include <iostream>
   
2. #include <vector>
   
3. #include <cmath>
   
4. using namespace std;
   
5. 
   
6. // 辗转相除法求最大公约数
   
7. int gcd(int a, int b) {
   
8.     while (b) {
   
9.         int temp = b;
   
10.         b = a % b;
    
11.         a = temp;
    
12.     }
    
13.     return a;
    
14. }
    
15. 
    
16. // 计算n的所有因子
    
17. vector<int> getFactors(int n) {
    
18.     vector<int> factors;
    
19.     for (int i = 1; i <= sqrt(n); ++i) {
    
20.         if (n % i == 0) {
    
21.             factors.push_back(i);
    
22.             if (i != n / i) {
    
23.                 factors.push_back(n / i);
    
24.             }
    
25.         }
    
26.     }
    
27.     return factors;
    
28. }
    
29. 
    
30. int main() {
    
31.     int x0, y0;
    
32.     cin >> x0 >> y0;
    
33.    
    
34.     if (y0 % x0 != 0) {
    
35.         cout << 0 << endl; // 如果y0不是x0的倍数，则不可能满足条件
    
36.         return 0;
    
37.     }
    
38.    
    
39.     int n = y0 / x0;
    
40.     vector<int> factors = getFactors(n);
    
41.     int count = 0;
    
42.    
    
43.     for (int a : factors) {
    
44.         int b = n / a;
    
45.         if (gcd(a, b) == 1) {
    
46.             count++;
    
47.         }
    
48.     }
    
49.    
    
50.     cout << count << endl;
    
51.     return 0;
    
52. }

复制代码