【SSLOJ】小清新期望题

题目

思路

设 \(i\) 的因子个数为 \(d_i\)。考虑一个 \(n\) 的排列，按照序列顺序从前往后删数。那么数字 \(i\) 能产生贡献当且仅当不存在一个 \(i\) 的因子在 \(i\) 的前面。
这种情况的期望为 \(\frac{(d_i-1)!}{d_i!}=\frac{1}{d_i}\)。
所以答案为

\[\sum^{n}_{i=1}\frac{1}{d_i} \]

对于 \(90\%\) 的数据，直接线性筛即可。
剩余 \(10\%\) 的数据 min_25 筛不会 /fad。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=20000010,M=1300010,MOD=998244353;
int n,m,prm[M],d[N],cnt[N],inv[M];
ll ans;

inline void findprm(int n)
{
	d[1]=1; cnt[1]=1;
	for (register int i=2;i<=n;i++)
	{
		if (!d[i])
		{
			d[i]=2; cnt[i]=1;
			prm[++m]=i;
		}
		for (register int j=1;j<=m;j++)
		{
			if (prm[j]*i>n) break;
			if (i%prm[j]==0)
			{
				cnt[i*prm[j]]=cnt[i]+1;
				d[i*prm[j]]=d[i]/(cnt[i]+1)*(cnt[i*prm[j]]+1);
				break;
			}
			else
			{
				cnt[i*prm[j]]=1;
				d[i*prm[j]]=d[i]*2;
			}
		}
	}
}

int main()
{
	scanf("%d",&n);
	inv[1]=1;
	for (int i=2;i<=1300000;i++)
		inv[i]=1LL*(MOD-MOD/i)*inv[MOD%i]%MOD;
	findprm(n);
	for (register int i=1;i<=n;i++)
		ans+=inv[d[i]];
	printf("%d",ans%MOD);
	return 0;
}