描述 给定两个正整数a和b,判断a和b是否互质(如果互质,那么a和b的最大公约数为1),互质则输出a和b互质,不互质则输出a和b的最小公倍数, 输入 输入两个正整数a和b,a,b<=10^310 3 输出 根据题目要求进行输出 输入样例 1 3 5 输出样例1 3和5互质 输入样例 2 4 6 输出样例2 12 c++代码
时间: 2024-04-14 13:30:01 浏览: 12
#include <iostream>
using namespace std;
// 计算最大公约数
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
// 计算最小公倍数
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
int main() {
int a, b;
cin >> a >> b;
if (gcd(a, b) == 1) {
cout << a << "和" << b << "互质" << endl;
} else {
cout << lcm(a, b) << endl;
}
return 0;
}
相关问题
给定两个正整数的最大公约数和最小公倍数
给定两个正整数的最大公约数和最小公倍数,可以通过以下公式求出这两个正整数:
设两个正整数为a和b,它们的最大公约数为d,最小公倍数为l,则有:
a = d * (a / d) * (b / d)
b = d * (l / d)
其中,a / d 和 b / d 互质,l = a * b / d。
因此,可以先求出最大公约数d,然后根据上述公式求出a和b。
给定正整数 n 和 k,有互质的整数 a、b 满足: 2 <= a < b <= n b = a + m * k, m为正整数 求 a 和 b 所有可能的数量有多少。
根据题意,我们可以得到:
b = a + m * k
因为 a 和 b 互质,所以 a 和 b 的最大公约数为 1,即:
gcd(a, b) = 1
根据裴蜀定理,对于任意正整数 a、b 和它们的最大公约数 d,存在整数 x 和 y,使得:
ax + by = d
因为 a 和 b 互质,所以 d = 1,即:
ax + by = 1
我们可以通过扩展欧几里得算法求出 x 和 y 的值,然后将其代入上式,得到:
a = a * x + b * y
因为 b = a + m * k,所以:
a = a * x + (a + m * k) * y
化简得:
a = (x + y) * a + m * k * y
因为 a 是正整数,所以:
x + y >
所以我们只需要枚举 x 和 y 的值,然后计算出对应的 a 和 b,判断是否满足条件即可。具体地,我们可以枚举 x 的值,然后通过扩展欧几里得算法求出 y 的值,然后计算出对应的 a 和 b,判断是否满足条件即可。最后统计满足条件的 a 和 b 的数量即可。
时间复杂度为 O(n * log n * log k)。