題目鏈接：點(diǎn)擊查看

題目大意：初始時(shí)有一個(gè) 1 ~ n 共 n 個(gè)元素的集合，現(xiàn)在需要選出恰好有 k 個(gè)元素的一個(gè)子集，使得子集中兩兩元素進(jìn)行 gcd 運(yùn)算后的最大值最小，分別輸出 k ∈[ 2 , n ] 時(shí)的答案

題目分析：讀完題后需要猜一個(gè)結(jié)論，那就是無論 k 的值為多少，取的數(shù)的順序?yàn)?#xff1a;

先取質(zhì)數(shù)，此時(shí) gcd_max = 1

再取使 gcd_max 不超過 2 的數(shù)

再取使 gcd_max 不超過 3 的數(shù)

......

直到 n 個(gè)數(shù)都取完

比賽的時(shí)候想到這里了，但是因?yàn)椴粫?shù)導(dǎo)致不會實(shí)現(xiàn)，那么到底該如何實(shí)現(xiàn)上述步驟呢？

第一步里的取質(zhì)數(shù)就不用多說了，打個(gè)表就能知道有多少個(gè)素?cái)?shù)，剩下的我們可以貪心去考慮，對于某個(gè)合數(shù) x ，如果我們接下來需要取 x 了，那么前提是 x 的所有因子都已經(jīng)取過了，不然取 x 的因子顯然是最優(yōu)的，既然 x 的所有因子都已經(jīng)取過了，那么取了 x 之后，此時(shí)再做 gcd 運(yùn)算的話，那么最大值肯定是 x 最大的那個(gè)因子

然后就可以直接實(shí)現(xiàn)了，對于每個(gè)合數(shù)找出其最大的因子就是答案了，找最大因子不太好找，我們可以先找到最小因子，然后做一下除法運(yùn)算就好了，找最小因子可以用歐拉篩或埃氏篩完成，鑒于時(shí)間復(fù)雜度足夠，且埃氏篩的實(shí)現(xiàn)比較簡單，所以放一下埃氏篩的代碼吧

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=5e5+100;vector<int>ans;int p[N];int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=2;i<=n;i++){if(!p[i]){ans.push_back(1);for(int j=i;j<=n;j+=i)if(!p[j])p[j]=j/i;}elseans.push_back(p[i]);}sort(ans.begin(),ans.end());for(int i=0;i<ans.size();i++)printf("%d ",ans[i]);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1333F Kate and imperfection(数论+贪心)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。