题目

题目描述
从 $[2, n]$ 中选出若干质数，记这些质数的集合为 $P$ 。定义集合 $S_P=\{kx\;|\;x\in P,\;k\in\N^+,\;k\leqslant\lfloor{n\over x}\rfloor\}$ ，即这些质数的倍数（不超过 $n$ 的）。

记 $f (S)$ 为，从集合 $S$ 中能选出的最多的数字个数，使得这些数字之间不存在倍数关系。现在请你求出 $\sum_{P}f(S_P)$ ，即对于所有可能的 $P$ 求出 $f(S_P)$ 的和。答案对 $998244353$ 取模。

数据范围与提示
$n\leqslant 10^{10}$ 。

思路

看题解，感觉是推导出来的，结果最后还是落脚到归纳法上了。我讨厌归纳法。

不如直接放结论：选择大于 $\lfloor{n\over 2}\rfloor$ 的所有可选数字。该方案显然合法，且不超过 $\lfloor{n\over 2}\rfloor$ 的可选数字必然存在大于 $\lfloor{n\over 2}\rfloor$ 的倍数，故肯定不可选。下证充分性。

调整法。若选择的最小数 $y\leqslant\lfloor{n\over 2}\rfloor$ ，尝试将其改为 $2 y$ 。若其因此成为另一数 $z$ 的倍数，即 $z\mid 2y$ ，由前提 $z\nmid y$ ，故必然有 $2\mid z$ 且 $\frac{z}{2}\mid y$ 。又由假设 $z > y$ 即 ${z\over 2}>\frac{y}{2}$ 为最小（可能的）真因子，所以唯一解是 $\frac{z}{2}=y$ ，与 $y, z$ 可以被同时选择矛盾。

当然，也可以看看题解的说法：若 $i\mid j$ 连边 $i\to j$ ，问题为最长反链长度 $=$ 最小链覆盖。结论是，找到最小没被覆盖的数 $x$ ，然后覆盖 $2^kx\;(k\in\N)$ 。结论的证明是，归纳法可知 $2 x$ 未被覆盖，此时若不覆盖 $2 x$ 以后还会需要一条链。

我比较好奇的是，怎么归纳的？而且 $2 x$ 确定要选了，那 $4 x, 8 x, 16 x$ 呢？😵

别管那么多了，还是回到结论上。对每个数字算贡献，即求 $x$ 何时可选。记 $c (x)$ 为 $x$ 的质因子个数，则只要任一质因子在 $P$ 中即可，剩余任选。记 $\pi(n)$ 为 $n$ 以内质数个数，则答案为
$\sum_{x=\lfloor{n\over 2}\rfloor+1}^n\big[2^{c(x)}-1\big]\cdot 2^{\pi(n)-c(x)}$
常数项 $2^{\pi(n)}$ 平凡。再提出 $-2^{\pi(n)}$ 后，仅余 $2^{-c(x)}$ 。显然它是积性函数，有 $f(p^k)={1\over 2}\;(k\in\N^+)$ ，用 $\tt min25$ 筛它就完事儿了！时间复杂度 $\mathcal O({n^{0.75}\over\ln n})$ 。

代码

#include <cstdio> // JZM yydJUNK!!!
#include <iostream> // XJX yydGOD!!!
#include <algorithm> // ZXY yydSISTER!!!
#include <cstring> // DYM yyd(OLD GOD)!!!
#include <cctype> // XYX yydLONELY!!! (the strong long for loneliness)
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar())
		if(c == '-') f = -f;
	for(; isdigit(c); c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}

const int MAXN = 100005;
int primes[MAXN], primes_size;
bool isPrime[MAXN];
void sieve(int n){
	memset(isPrime+2,true,n-1); rep(i,2,n){
		if(isPrime[i]) primes[++ primes_size] = i;
		for(int j=1; j<=primes_size&&primes[j]<=n/i; ++j){
			isPrime[i*primes[j]] = false;
			if(i%primes[j] == 0) break;
		}
	}
}

const int MOD = 998244353, inv2 = (MOD+1)>>1;
inline int qkpow(llong b,int q){
	llong a = 1;
	for(; q; q>>=1,b=b*b%MOD)
		if(q&1) a = a*b%MOD;
	return int(a);
}

int haxi[2][MAXN]; ///< use with @a _id
# define _id(x) ((x) < MAXN ? haxi[0][x] : haxi[1][n/(x)])
llong w[MAXN<<1]; int g[MAXN<<1];
void step_one(llong n){
	static int tot; tot = 0;
	for(llong i=1; i<=n; i=n/w[tot]+1){
		w[++ tot] = n/i, _id(w[tot]) = tot;
		g[tot] = int((w[tot]-1)%MOD); // number of primes
	}
	for(int j=1; j<=primes_size&&primes[j]<=n/primes[j]; ++j)
		for(int i=1; i<=tot&&primes[j]<=w[i]/primes[j]; ++i){
			g[i] -= g[_id(w[i]/primes[j])]-j+1;
			if(g[i] < 0) g[i] += MOD; // keep positive
		}
}
llong step_two(const llong &n,llong x,int i){
	if(primes[i] > x) return 0;
	llong sum = llong(g[_id(x)]+MOD-i+1)*inv2%MOD;
	for(; i<=primes_size&&primes[i]<=x/primes[i]; ++i)
		for(llong t=primes[i],nxt=x/t; t<=nxt; t*=primes[i])
			sum = (sum+(1+step_two(n,x/t,i+1))*inv2)%MOD;
	return sum; // just answer
}

int main(){
	llong n; scanf("%lld",&n);
	sieve(MAXN-5); step_one(n);
	const int coe = qkpow(2,g[1]);
	llong ans = (n-step_two(n,n,1)+MOD)%MOD;
	step_one(n >>= 1); ans += step_two(n,n,1);
	printf("%lld\n",(ans+MOD-n%MOD)*coe%MOD);
	return 0;
}

后记

我们永远滴神 $\sf{Rainybunny}$ 自然是轻松发现结论。事实上，所有人都能轻松发现结论；在角落有一句注脚： $\sf OneInDark$ 除外。

这让我有点想起另一道题： $[2, n]$ 每个数字最多用一次，找出尽可能多的数字对 $a_i,b_i)$ 使得 $a_i,b_i$ 不互质。做法是，对于奇质数 $p$ ，将其倍数全部匹配——若有奇数个，保留 $2 p$ 。那么最后剩下一群偶数，任意匹配。最多剩下一个有用数字（大于 $\lfloor{n\over 2}\rfloor$ 的质数是无用的），故为答案下界。题目名已失落。