数的集合 - 正经题解

建议降 黄/橙。

分类讨论：

这个数是不是质数？是？那就没得操作了，直接输出 $0$。

如果不是质数，那他有没有为 $2$ 的质因子？

有：那就能把所有 $2\times i(2\times i \le N)$ 的数都给加进这个集合内，然后所有 $i(2\times i \le N)$ 也都进去了。

没有：那就把其中一个质因子 $\times 2$ 放进集合内，可以证明它必定小于 $N$。然后就和上面的一样了。

当 $N$ 足够大时（$N\ge 3^2$ 就行），显然不能进入集合的只有所有 $\gt \lfloor N/2\rfloor$ 的质数。显然这可以前缀和秒掉。

#include <iostream>
#include <cstdio>
using namespace std;
bool vis[3000005];
int qzh[3000005];
int dabiao[10]{0, 0, 0, 0, 1, 0, 3, 0, 4, 5};
void solve(){
	int n;
	cin >> n;
	if(n < 10){
		cout << dabiao[n] << '\n';//小数据打表，以免出现特殊情况
		return;
	}
	if(!vis[n]) cout << "0\n";//是质数，操作次数为0
	else cout << n - qzh[n] + qzh[n / 2] - 2 << '\n';//否则就按题意模拟
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	vis[0] = vis[1] = 1;
	for(int i = 2; i <= 1800; i++){//筛
		if(!vis[i]){
			for(int j = i * 2; j <= 3000000; j += i) vis[j] = 1;
		}
	}
	for(int i = 2; i <= 3000000; i++){
		qzh[i] = qzh[i - 1] + 1 - vis[i];//记录前缀和
	}
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度 $O(N\ln\ln N+T)$。