题目描述

给定两个不同的正整数 a,b，判断它们是否互质。

样例

样例输入1

5
2 3 4 6 9

样例输出1

4

样例输入2

9
1 2 3 5 6 7 8 9 10

样例输出2

4

算法1：暴力枚举

时间复杂度(暴力枚举) $O(n^2)$

C++ 代码

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<math.h>
#include<string>
#include<cstring>
#include<string.h>
#include<cstdio>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<limits.h>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<time.h>
#include<ctime>
#include<list>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
ll a,b;
int main(){
    scanf("%lld%lld",&a,&b);
    for(ll i=2;i<=min(a,b);i++){
        if(a%i==0&&b%i==0){
            printf("NO\n");
            return 0;
        }
    }
    printf("YES\n");
    return 0;
}

算法2：拓展欧几里得算法

时间复杂度(欧几里得算法) $O(log2n)$

（之前好像看到过复杂度是这个，但是不确定了）

参考文献

见度娘

C++ 代码

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<math.h>
#include<string>
#include<cstring>
#include<string.h>
#include<cstdio>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<limits.h>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<time.h>
#include<ctime>
#include<list>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
ll gcd(ll x,ll y){
    if(y==0)    return x;
    return gcd(y,x%y);
}
ll a,b;
int main(){
    scanf("%lld%lld",&a,&b);
    if(gcd(a,b)==1) printf("YES\n");
    else            printf("NO\n");
    return 0;
}