狄利克雷卷积

定义：
即：两个积性函数的狄利克雷卷积仍为积性函数。


数论函数是积性及加性函数。
运算法则：

狄利克雷卷积的时间复杂度： $O(n\ast logn)$O(n∗logn)

计算狄利克雷卷积 $h\left(n\right)$h(n)：
如果再像暴力计算那样，复杂度将达到恐怖的 $O\left(n\sqrt{n}\right)$O(nn ​)。
但是我们可以从质数筛（埃式筛）的想法入手，我们可以直接枚举一个i，再为它的倍数上的值加上对应的贡献就好。
时间复杂度 $O\left(nlogn\right)$O(nlogn)。

void Dirichlet(int f[],int g[],int ans[],int n)
{
    memset(ans,0,sizeof ans);
    for(int i=1;i<=n;i++)
        for(int j=1;i*j<=n;j++)
            ans[i*j]+=f[i]*g[j];
}

常用的狄利克雷卷积和积性函数
附上一篇博客，便于学习

例题：
Clarke and math HDU - 5628
(1). $n\ast logn\ast logk$n∗logn∗logk做法：
可以发现，原式子的每一层都可以视为一个狄利克雷卷积的形式，其中函数 $h=1$h=1，所以最终式子可以化简为 $g=f\ast h^k$g=f∗hk。利用快速幂和狄利克雷卷积即可计算出结果。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int mod=1e9+7;
ll f[N],h[N],res[N],t[N];
void mul(ll a[],ll b[],int n)
{
    memset(t,0,sizeof(t));
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j+=i)
            t[j]=(t[j]+a[i]*b[j/i])%mod;
    }
    for(int i=1;i<=n;i++)
        a[i]=t[i];
}
void power(ll a[],int b,int n)
{
    memset(res,0,sizeof(res));
    res[1]=1;
    while(b)
    {
        if(b&1)
            mul(res,a,n);
        mul(a,a,n);
        b>>=1;
    }
}
int main()
{
    int t,n,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&f[i]);
            h[i]=1;
        }
        power(h,k,n);
        mul(f,res,n);
        for(int i=1;i<=n;i++)
            printf("%lld%c",f[i],i==n?'\n':' ');
    }
    return 0;
}

$\left(2\right)nlogn$(2)nlogn的做法：（待学）
链接

Dirichlet $k$k-th root Gym - 102471C
具体见ec final题解。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int p=998244353;
ll g[N],f[N],t[N];
void read(ll &x)
{
    char cc;
    int f=1;
    cc=getchar();
    while(cc<'0'||cc>'9')
    {
        if(cc=='-')
            f=-1;
        cc=getchar();
    }
    while(cc>='0'&&cc<='9')
    {
        x=10*x+cc-'0';
        cc=getchar();
    }
    x=x*f;
}
ll power(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)
            res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res%p;
}
void mul(ll a[],ll b[],int n)
{
    memset(t,0,sizeof(t));
    /*for(int i=1;i<=n;i++):Time limit exceeded on test 26 牛客:599ms { for(int j=i;j<=n;j+=i) t[j]=(t[j]+a[i]*b[j/i]%p)%p; }*/
    /*for(int i=1;i<=n;i++):936ms { for(int j=1;j*i<=n;j++) t[i*j]=(t[i*j]+a[i]*b[j]%p)%p; }*/
    for (int i=1;i*i<=n;i++) {//686ms
        t[i*i]=(t[i*i]+a[i]*b[i]%p)%p;
        for (int j=i+1;i*j<=n;j++) {
            t[i*j]=(t[i*j]+a[i]*b[j]%p+a[j]*b[i]%p)%p;
        }
    }
    for(int i=1;i<=n;i++)
        a[i]=t[i];
}
void qpow(ll a[],ll b,int n)
{
    f[1]=1;
    while(b)
    {
        if(b&1)
            mul(f,a,n);
        mul(a,a,n);
        b>>=1;
    }
}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        read(g[i]);
        f[i]=0;
    }
    ll inv=power((ll)k,(ll)p-2);//k的逆元
    qpow(g,inv,n);
    for(int i=1;i<=n;i++)
        printf("%lld%c",f[i],i==n?'\n':' ');
    return 0;
}