四月月赛H题

题目

最小互质数

我们定义两个数的互质数当且仅当gcd(a, b) = 1。
现在L手里有n个数，分别为a1，a2，a3 ……an-1，an 。
问，没有在这n个数中出现过并且与这n个数都互质的最小的数是多少。
LL觉得这个问题太简单了，于是她把这个问题交给你来解决
输入
第一行一个数n (1 ≤ n, ai ≤ 10^5)
接下来n行，每行一个数，分别代表a1，a2，a3 ……an-1，an 。
输出
输出一行代表答案
样例输入
5
1
2
3
4
5
样例输出
7

解题思路

这道题如果用暴力破解肯定会TLE，所以我是先用欧拉筛法标记好10^6以内的素数。然后再用sort函数给输入的数据排好序，从1开始按顺序一一往后查找，只要一出现数组中没有的数，就判断是否是质数（利用前面欧拉筛法标记好的的素数数组），如果是质数，就判断其是不是数组中出现过的数的约数，如果不是那么这个数就是答案，如果是，就继续往后找。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 1000005
using namespace std;

int prim[N],a[N],i,j,k,n,cnt=0;
bool isp[N]={false};
int main()
{
    //欧拉筛法求2~N之间的素数
    for(i=2;i<=N;i++){
        if(!isp[i]) prim[++cnt]=i;
        for(int j=1;j<=cnt;j++){
            if(i*prim[j]>N) break;
            isp[i*prim[j]]=true;
            if(i%prim[j]==0) break;
        }
    }

    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);

    sort(a+1,a+1+n);
    if(a[1]!=1){
        printf("1");//如果数组中最小的数不是1，则这n个数的最小互质数肯定为1
        return 0;
    }

    for(i=2,k=2;;i++,k++){
        bool f=0;
        while(a[i+1]!=k+1){//如果a[i+1]!=k+1,则k+1是这个有序数组没有出现过的数
            if(!isp[k+1]){//判断是否为素数
                if(k+1>a[n]){//如果k+1大于数组里最大的数，那么它肯定不可能是数组里任何一个数的约数
                    printf("%d\n",k+1);
                    return 0;
                }
                for(j=i+1;j<=n;j++){//判断数组里有没有数能被k+1整除
                    if(a[j]%(k+1)==0){
                        break;
                    }
                }
                if(j>n){//数组内没有数能被k+1整除，输出k+1
                    printf("%d\n",k+1);
                    return 0;
                }
            }
            k++;//若不符合最小互质数条件，则继续往后查找
        }
    }
    return 0;
}