CF1333 F Kate and imperfection（数论）

题意

$[1,n]$[1,n] 中，任选 $k$k 个数，求两两 $gcd$gcd 的最大值的最小值。
分别对 $k=2,3,...,n$k=2,3,...,n 求取答案。
$n\le 500000$n≤500000

分析

一个数 $x$x 放入集合时，它的所有因子一定都在集合中。否则，我们可以用它的某一个因子来代替它，结果只可能更好。这是个很重要的性质，意味着如果 $x$x 在集合中，那么它参与的 $gcd$gcd 一定是它本身或是它的最大公因子。
那么考虑答案为 $x$x 时，它一定是集合中某些数的因子。而且这些数的所有因子都在集合中。因此 $x$x 是这些数的最大真因子。所以答案为 $x$x 时，以 $x$x 为最大真因子的数一定都在集合中。
然后 $1$1 的出现次数就是 $1$1 作为最大真因子的次数， $2$2 出现次数就是 $2$2 作为最大真因子的次数， $x$x 的出现次数就是 $x$x 作为最大真因子的出现次数。

代码如下

#include <bits/stdc++.h>
#define N 500005
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
LL z = 1;
int read(){
	int x, f = 1;
	char ch;
	while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
	x = ch - '0';
	while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
	return x * f;
}
int ksm(int a, int b, int p){
	int s = 1;
	while(b){
		if(b & 1) s = z * s * a % p;
		a = z * a * a % p;
		b >>= 1;
	}
	return s;
}
int p[N], x[N], c[N], cnt, maxn = N - 5;
LL t;
int main(){
	int i, j, n, m;
	for(i = 2; i <= maxn; i++){
		if(!x[i]) x[i] = p[++cnt] = i;
		for(j = 1; j <= cnt; j++){
			t = z * i * p[j];
			if(t > maxn) break;
			x[t] = p[j];
			if(i % p[j] == 0) break;
		}
	}
	n = read();
	for(i = 2; i <= n; i++) c[i / x[i]]++;
	for(i = 1; i <= n; i++){
		for(j = 1; j <= c[i]; j++) printf("%d ", i);
	}
	return 0;
}