P11253 [GDKOI2023 普及组] 小学生数学题题解

DengDuck · 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;
}

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

P11253 [GDKOI2023 普及组] 小学生数学题 题解

P11253 [GDKOI2023 普及组] 小学生数学题题解