3260: 【III级】【欧几里德算法】判断互质

3260: 【III级】【欧几里德算法】判断互质

时间限制: 1 Sec   内存限制: 128 MB

题目描述

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

输入

输入两个整数m和n（1<=n,m<2^31），中间用空格隔开。

输出

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

样例输入 Copy

36 56

样例输出 Copy

No

解析：判断互质有很多方法，我们这里就用最典型的辗转相除法做。

#include<bits/stdc++.h>

using namespace std;

long long gcd(long long a,long long b){

//cout<<a<<' '<<b<<endl;

if(b==0) return a;

else return gcd(b,a%b);

}

int main(){

long long m,n;

cin>>m>>n;if(m<n){long long c=m;m=n;n=c;}

if(gcd(m,n)==1) printf("Yes\n");

else printf("No\n");

return 0;

}