傳送門
文章目錄
題意：
n≤5e5n\le5e5n≤5e5
思路：
首先有個顯然的結論：當往集合中加入一個數(shù)xxx的時候，如果存在d∣xd|xd∣x且ddd不在集合中，那么加入ddd一定比加入xxx更優(yōu)。
也就是說當我們加入xxx的時候，xxx的真因子一定都在集合中，那么我們對[1,n][1,n][1,n]求每個數(shù)求最大真因子是多少，讓后排個序輸出即可。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
;
int nt
[N
],prime
[N
],tot
;
int cnt
[N
],ans
[N
];
bool st
[N
];void get_prime(int n
) {for(int i
=1;i
<=n
;i
++) nt
[i
]=i
;for(int i
=2;i
<=n
;i
++) {if(!st
[i
]) prime
[++tot
]=i
;for(int j
=i
+i
;j
<=n
;j
+=i
) st
[j
]=true,nt
[j
]=min(nt
[j
],i
);}
}int main()
{
cin
>>n
;get_prime(n
+10);for(int i
=1;i
<=n
;i
++) nt
[i
]=i
/nt
[i
];sort(nt
+1,nt
+1+n
);for(int i
=2;i
<=n
;i
++) printf("%d ",nt
[i
]);return 0;
}
總結
以上是生活随笔為你收集整理的Codeforces Round #632 (Div. 2) F. Kate and imperfection 数论 + 贪心的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
