最大公约数与最小公倍数问题
输入两个正整数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;
}
似乎并不正确。 最大公约数与最小公倍数计算
要计算两个正整数 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 小助理，如未能正确解答您的问题，请继续追问。 试试这个？
#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;
}
页:
[1]