WZOI-221判断互质

题目描述:

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

输入格式:

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

输出格式:

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

样例输入:

36 56

样例输出:

No

提示:

1<=n,m<2^31

使用辗转相除法求出A、B的最大公约数（也就是最大公因数）。

欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。计算公式gcd(a,b) = gcd(b,a mod b)。

时间限制: 1000ms
空间限制: 256MB

代码如下：
 

#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,r;
	cin>>a>>b;
	while(1){
		r=a%b;
		if(r==0){
			if(b==1){
				cout<<"Yes";
				break;
			}else{
				cout<<"No";
				break;
			}
			
		}
		a=b;
		b=r;
	}
	return 0;
}