牛客2020跨年场 C-最小互质数 筛法


传送门

题意:

我们定义两个数互质当且仅当gcd(a, b) = 1。

现在qcjj手里有n个数,分别为$a_1, a_2, a_3 \dots a_{n - 1}, a_{n}$。
问,没有在这n个数中出现过并且与这n个数都互质的最小的数是多少。
qcjj觉得这个问题太简单了,于是她把这个问题交给你来解决。

题解:

分两种情况讨论,若输入的数字中没有1,则直接输出1

若输入的数字中有1,则对除1以外的数分解质因数,然后筛去含有这些因子的数

另外,虽然输入的a不大于1e5,但是答案可能大于1e5,实际上最大可能为1e5后面的第一个质数

#include<iostream>
using namespace std;
bool mapp[1000005];
int a[1000005];
int gcd(int a,int b){
    if(b==0)return a;
    else return gcd(b,a%b);
}
int main(){
    int n;
    scanf("%d",&n);
    int flag=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]==1){flag=1;
            continue;}
        mapp[a[i]]=1;
        int t=a[i];
        for(int j=2;1LL*j*j<=t;j++){
            while(t%j==0){
                t/=j;
                mapp[j]=1;
            }
        }
        if(t>1)mapp[t]=1;
    }
    if(flag==0){
        printf("1\n");
        return 0;
    }
    for(int i=2;i<=1000000;i++){
        if(mapp[i]==0){
            printf("%d\n",i);
            return 0;
        }else if(i!=1){
            for(int j=2*i;j<=1000000;j+=i)mapp[j]=1;
        }
        /*for(int j=1;j<=n;j++){
            if(i==a[j] || gcd(a,b))
        }*/
    }
    
    return 0;
}

 

上一篇:CF1557A题解


下一篇:C++多继承导致的菱形继承问题