题目大意: 给定f（1~n），求g(1~n)
题目分析：（狄利克雷卷积） 狄利克雷卷积： 狄利克雷卷积满足：交换律，结合律，分配率等性质（和乘法是一样的）。
我们设函数g(i)=1 如果k==1，则 i 的答案为： (f∗g)(n)=∑d1|nf(d1) ( f ∗ g ) ( n ) = ∑ d 1 | n f ( d 1 ) 如果k==2，则 i 的答案为： ((f∗g)∗g)(n)=∑d1|n∑d2|d1f(d2) ( ( f ∗ g ) ∗ g ) ( n ) = ∑ d 1 | n ∑ d 2 | d 1 f ( d 2 ) 以此类推 则最终答案为 f∗(gk) 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; }