题目大意: 给定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 ) (f*g)(n)=\sum_{d_1|n}{f
狄利克雷卷积 约定 n = p 1 a 1 p 2 a 2 ⋯ p r a r \ n=p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{r}^{a_{r}} n=p1a1p2a2⋯prar a ∣ b \ a \mid b a∣b: a \ a a整除 b \ b b a ∤ b \ a \nmid b a∤b: a \ a a不整