狄利克雷卷积【HDU5628】Clarke and math

本文主要是介绍狄利克雷卷积【HDU5628】Clarke and math，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意:
这里写图片描述
给定f（1~n），求g(1~n)

题目分析：（狄利克雷卷积）
狄利克雷卷积：
这里写图片描述
狄利克雷卷积满足：交换律，结合律，分配率等性质（和乘法是一样的）。

我们设函数g(i)=1
如果k==1，则 i 的答案为： $(f*g)(n)=\sum_{d_1|n}{f(d_1)}$
如果k==2，则 i 的答案为： $((f*g)*g)(n)=\sum_{d_1|n}\sum_{d_2|d_1}{f(d2)}$
以此类推
则最终答案为 $f*(g^k)$

所以只要求logk次狄利克雷卷积就可以了。
但是如果是枚举i，枚举i的约数，时间复杂度为n^2,明显接受不了。
所以我们直接枚举约数，然后枚举该约数和哪些数相乘。
这样时间复杂是nlogn的。

总时间复杂度O（nlognlogk）

代码如下：

#include <cstdio>
#define N 120000
using namespace std;
const int mod=1e9+7;
int T,n,k;
struct fun{int a[N];void make_f(){for(int i=1;i<=n;i++)scanf("%d",&a[i]);}void make_g(){for(int i=1;i<=n;i++)a[i]=1;}fun operator * (const fun &c) const{static fun z;for(int i=1;i<=n;i++) z.a[i]=0;for(int i=1;i*i<=n;i++)for(int j=i;j*i<=n;j++){z.a[i*j]+=1ll*a[i]*c.a[j]%mod,z.a[i*j]%=mod;if(i!=j) z.a[i*j]+=1ll*a[j]*c.a[i]%mod,z.a[i*j]%=mod;}return z;}void print(){printf("%d",a[1]);for(int i=2;i<=n;i++)printf(" %d",a[i]);printf("\n");}
};
void Fast_Power(fun &ans,fun a,int k)
{while(k){if(k&1) ans=ans*a;a=a*a;k>>=1;}
}
int main()
{scanf("%d",&T);while(T--){scanf("%d%d",&n,&k);fun f,g;f.make_f();g.make_g();Fast_Power(f,g,k);f.print();}return 0;
}