2019 ICPC Asia-East Continent Final C Dirichlet k-th root

Dirichlet k-th root

Example
input
5 2
1 8 4 26 6
output
1 4 2 5 3

题意

先给结论，$f^{mod+1}=ϵ(f(1))*f，f^{mod}=ϵ(f(1))$fmod+1=ϵ(f(1))∗f，fmod=ϵ(f(1))，因为题目保证f(1)=1,以下直接以1替代。即自卷mod+1次就回到了起点。

这个结论意味着 $f^{k*inv(k)}=f$fk∗inv(k)=f，因为根据结论可知，$f^{p*mod+1}=f$fp∗mod+1=f ，若满足$q*k=p*mod+1$q∗k=p∗mod+1（p,q为任意值），则 $f^{q*k}$fq∗k 就是答案，而这个式子 $q*k-p*mod=1$q∗k−p∗mod=1 就是扩展欧几里得，根据逆元的定义，此时q就是k模mod的逆元，即q=inv(k)，因此设 $F=f^{k},F^{inv(k)}$F=fk,Finv(k) 即为答案。

证明 $f^{mod}=ϵ$fmod=ϵ 有个较为暴力的办法 ,可以尝试直接拆开 $f^{mod}$fmod，会发现：
当 i > 1 时，$f^{mod}(i)$fmod(i) 即数组第i项的多项式里，每一项的系数都是mod（惯例显然易证），取模当然等于0。
当 i = 1 时，$f^{mod}(1)=f(1)^{mod}\%mod=f(1)=1$fmod(1)=f(1)mod%mod=f(1)=1，因此得证$f^{mod}=ϵ$fmod=ϵ

题外：若 $f(1)!=1$f(1)!=1 ,则结论是 $f^{p*mod+1}=ϵ(f(1)^p)*f$fp∗mod+1=ϵ(f(1)p)∗f

代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll mod = 998244353;
const int N=2e5+5;
ll da[N],db[N], ans[N];
int n, k;

ll ksm(ll a,ll k,ll mod)
{
    int s=1,b=a;
    for(;k;k>>=1,b=1ll*b*b%mod)
        if(k&1) s=1ll*s*b%mod;
    return s;
}

void mul(ll x[], ll y[]) {
    memset(db,0,sizeof(db));
    int len=sqrt(n);
    for (int i=1;i<=len;i++) {
        db[i*i]=(db[i*i]+x[i]*y[i]%mod)%mod;
        for (int j=i+1;i*j<=n;j++)
            db[i*j]=(db[i*j]+x[i]*y[j]%mod+x[j]*y[i]%mod)%mod;
    }
    for (int i=1;i<=n;i++)x[i]=db[i];
}

void solve(int p) {
    memset(ans,0,sizeof(ans));
    ans[1] = 1;
    while(p){
        if(p%2)mul(ans, da);
        mul(da, da);
        p/=2;
    }
}
int main() {

    scanf("%d%d",&n,&k);
    for (int i =1;i<=n;i++)
        scanf("%I64d",&da[i]);
    solve(ksm(k,mod-2,mod));
    for (int i = 1; i <= n; i++)
        printf("%I64d ",ans[i]);
    return 0;
}