题目描述

小学数学教材对互质数是这样定义的：“公约数只有 1 的两个数，叫做互质数。”

给定两个不同的正整数 a,b，请你判断它们是否互质。

输入格式
共一行，包含两个不同的正整数 a,b。

输出格式
如果 a,b 互质，则输出 YES，否则输出 NO。

数据范围
前三个测试点满足 1≤a,b≤10。
所有测试点满足 1≤a,b≤100。

输入样例1：
2 3
输出样例1：
YES
输入样例2：
2 4
输出样例2：
NO

样例

blablabla

include [HTML_REMOVED]

using namespace std;

// 函数：计算最大公约数
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}

int main() {
int a, b;
cin >> a >> b; // 输入两个不同的正整数

// 判断是否互质
if (gcd(a, b) == 1) {
    cout << "YES" << endl; // 互质
} else {
    cout << "NO" << endl; // 不互质
}

return 0;

}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla