1028.判断互质

CCF NOI 1028.判断互质

题目描述 输入两个正整数m和n，判断m和n是否互质（即最大公约数为1），是则输出Yes，否则输出No。

输入 输入两个整数m和n，中间用空格隔开。

输出 如互质输出Yes，否则输出No。

样例输入：36 56

样例输出：No

数据范围限制：1<=n,m<2^31

题目分析

1. m,n取值范围都极大，无法通过暴力计算
2. 判断互质的标准为最大公约数是否为1

---

#include<iostream>

using namespace std;

int main() {

	int m, n;
	cin >> m >> n;

	int a = m, b = n, ok = 1, max, r, q;
	while (ok) {
		r = a % b;
		q = a / b;
		if (!r) {
			max = b;
			ok = 0;
		}
		else {
			a = b;
			b = r;
		}
	}

	if (max == 1)cout << "Yes";
	else cout << "No";

	return 0;
}