解法：我们观察这个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 ? ‘\n‘ : ‘ ‘); } return 0; }
HDU-5628 Clarke and math-狄利克雷卷积+快速幂
原文：https://www.cnblogs.com/clno1/p/11599344.html