本文主要是介绍D-又是一年毕业季(牛客月赛99,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:有长度为n的数组a,求对所有数字取模都不等于0的最小数字(x>=2)
分析:算出最小的且不在数组里的素数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e6+10;
bool is_prime[N];
ll n;
vector<int> prime;
void Eratosthenes(ll n) {is_prime[0] = is_prime[1] = false;for (int i = 2; i <= n; ++i) is_prime[i] = true;for (int i = 2; i <= n; ++i) {if (is_prime[i]) {prime.push_back(i);if ((long long)i * i > n) continue;for (int j = i * i; j <= n; j += i)is_prime[j] = false;}}
}
void sol(){map<ll,ll>mp;cin>>n;for(int i=1;i<=n;i++){ll x;cin>>x;mp[x]=1;}for(auto &x:prime){if(mp[x]!=1){cout<<x<<endl;return;}}
}
int main(){int t;cin>>t;Eratosthenes(N);while(t--)sol();
}
这篇关于D-又是一年毕业季(牛客月赛99的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!