题目大意: 给定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

这题以前用快速幂写的 今天用线性筛写了一下，真刺激 大概就是说那个东西是 f∗1k f ∗ 1 k f*1^k 然后你只要算出来 1k 1 k 1^k 就可以 O(nlogn) O ( n l o g n ) O(nlogn)卷积了 关于算 1k 1 k 1^k当然可以直接快速幂 O(nlognlogk+nlogn) O ( n l o g n l o g k + n