Datahub
数据改变生活

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

发表时间:2022-10-28 23:22

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

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

题目描述

输入两个正整数mn,判断mn是否互质(即最大公约数为1),是则输出Yes,否则输出No

输入

输入两个整数mn1<=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;

}


文章分类: 算法例题
分享到:
QQ:258506508                                     联系电话:020-000000    000-000000                                   联系邮箱:xxx@.co.m                                     联系地址:XXX省XXX市XXX县XXX路