自动搬运

查看原文

来自洛谷，原作者为

	DengDuck 澳門現役 OIer，萌萌未花日奈雙推人一枚

搬运于2025-08-24 23:05:45，当前版本为作者最后更新于2024-11-07 20:02:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

下面我将给出 @DeepSeaSpray 当年在 GDKOI 现场讲题的视频，请忽视我的鬼叫。

简单来说，我们有 $a^{-k}b^{-k}=(ab)^{-k}$，因此发现 $F(i)=i^{-k}$ 是完全积性函数，可以用线性筛在 $\mathcal O(n)$ 内解决。

具体方式是对于质数求 $k$ 次方的逆元，其他数字在线性筛的过程中可以拆分成两个更小的数字的乘积，于是就可以求出来了。

对于阶乘显然可以直接线性求，所以总的时间复杂度是 $\mathcal O(n)$。

下面是我很久之前写的实现，很丑：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL mod=998244353;
inline LL ksm(LL x,LL y)
{
	LL ans=1;
	while(y)
	{
		if(y&1)ans=ans*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ans;
}
const int N=2e7+5;
LL n,k,pw[N],fac,ans;
int tot[N],cnt,b[N];

int main()
{
	cin>>n>>k;
	pw[1]=1,fac=1;
	for(int i=2;i<=n;i++)
	{
		if(!b[i])
		{
			b[i]=i;
			tot[++cnt]=i;
			pw[i]=ksm(ksm(i,mod-2),k);
		}
		for(int j=1;tot[j]*i<=n&&j<=cnt&&tot[j]<=b[i];j++)
		{
			b[tot[j]*i]=tot[j];
			pw[tot[j]*i]=pw[tot[j]]*pw[i]%mod; 
		}
	}
	for(int i=1;i<=n;i++)
	{
		ans=(ans+fac*pw[i]%mod)%mod; 
		fac=fac*(i+1)%mod; 
	}
	cout<<ans<<endl;
}

真的好想念初二的美好时光啊，但是已经回不去了......