[2019 EC-Final] C. Dirichlet kk-th root (狄利克雷卷积的性质+快速幂)

题意：

给定n和k，给定一个数论函数(g)的前n项，找到这样一个数论函数(f)使得(f^k=g)(在狄利克雷卷积意义下，mod p意义下)(p为质数),打印(f)的前n项。（保证(g(1)=1)）

解法：

在(g(1)=1)的条件下可以由(f^k=g)推出(f=g^{1/k})((1/k是k的逆元))，然后就可以利用套了快速幂的卷积在(O(logN*logN*N))的时间内求出

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+5;
const ll mod = 998244353;
ll fp(ll b,ll p){
    ll ans=1;
    while(p){
        if(p&1)ans=ans*b%mod;
        b=b*b%mod;
        p>>=1;
    }
    return ans;
}
ll a[maxn],ans[maxn];
ll n,k;
ll temp[maxn];
void mul(ll *a,ll *b){//n*logn
    for(ll i=1;i<=n;i++)temp[i]=0;
    for(ll i=1;i<=n;i++){
        for(ll j=1;i*j<=n;j++){
            temp[i*j]=(temp[i*j]+a[i]*b[j])%mod;
        }
    }
    for(ll i=1;i<=n;i++)a[i]=temp[i];
}
void solve(){
    ans[1]=1;
    while(k){
        if(k&1)mul(ans,a);
        mul(a,a);
        k>>=1;
    }
}
int main () {
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    k=fp(k,mod-2);
    solve();
    for(int i=1;i<=n;i++){
        if(i>1)printf(" ");
        printf("%lld",ans[i]);
    }
}