前置知识
解法
观察到 \(f(i)=\frac{1}{i^{k}} \bmod p\) 是完全积性函数,线性筛预处理即可。
需要适当的取模优化。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
const ll p=998244353;
ll prime[3000010],inv[20000010],len=0;
bool vis[20000010];
ll qpow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1)
{
ans=ans*a%p;
}
b>>=1;
a=a*a%p;
}
return ans;
}
void isprime(ll n,ll k)
{
memset(vis,0,sizeof(vis));
inv[1]=1;
for(ll i=2;i<=n;i++)
{
if(vis[i]==0)
{
len++;
prime[len]=i;
inv[i]=qpow(qpow(i,k),p-2);
}
for(ll j=1;j<=len&&i*prime[j]<=n;j++)
{
vis[i*prime[j]]=1;
inv[i*prime[j]]=inv[i]*inv[prime[j]]%p;
if(i%prime[j]==0)
{
break;
}
}
}
}
int main()
{
ll n,k,ans=0,mul=1,i;
cin>>n>>k;
isprime(n,k);
for(i=1;i<=n;i++)
{
mul=mul*i%p;
ans=(ans+mul*inv[i]%p)%p;
}
cout<<ans<<endl;
return 0;
}
标签:GDKOI2023,题解,ll,long,vis,ans,P11253,define
From: https://www.cnblogs.com/The-Shadow-Dragon/p/18535965