HDU-5628 Clarke and math-狄利克雷卷积+快速幂

 解法：我们观察这个g(i)的式子。我们设h(i)=1发现：

当k=1，g=sigma(i1|i) f(i1) = sigma(i1|i) f(i1) * h(i/i1) =Dirchlet ( h* f )

当k=2，g=sigma(i2|i1) f(i2) = Dirchlet( h * Dirchlet(h * f ) )

......

当k=k，g= Dirchlet( h * Dirchlet( h * Dirchlet(h * f) ) )  里面有k个括号

其实就是  g=h * h *h ...* f  (*代表狄利克雷卷积)

学过狄利克雷卷积应该知道是满足结合律的，那么我们就用快速幂计算 h^k ，最后再做一次卷积就能得到结果。

注意要储存h^k的数组g必须g[1]=1才能存下来。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
const int MOD=1e9+7;
int n,k;
LL f[N],g[N],h[N];

LL c[N];
void Dirch(LL *a,LL *b) {  //计算a=a*b的狄利克雷卷积 
    memset(c,0,sizeof(c));
    for (int i=1;i<=n;i++)
        for (int j=i;j<=n;j+=i)
            c[j]=(c[j]+a[i]*b[j/i]%MOD)%MOD;
    memcpy(a,c,sizeof(c));        
}

int main()
{
    int T; cin>>T;
    while (T--) {
        scanf("%d%d",&n,&k);
        for (int i=1;i<=n;i++) scanf("%d",&f[i]);
        for (int i=1;i<=n;i++) h[i]=0,g[i]=1;
        h[1]=1;
        for (;k;k>>=1) {
            if (k&1) Dirch(h,g);
            Dirch(g,g);
        }
        Dirch(f,h);
        for (int i=1;i<=n;i++) printf("%lld%c",f[i],i==n ? '
' : ' ');
    }
    return 0;
}