3260: 【III级】【欧几里德算法】判断互质发表时间:2022-10-28 23:22 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; } 上一篇14418: 找素数
文章分类:
算法例题
|