一般函数 \(\times\) 一般函数 \(O(n\log n)\)
暴力即可，\(O(n\log n)\)
一般函数 \(\times\) 积性函数 \(O(n\log \log n)\)
对每一个指数跑类似 FWT 的东西，\(O(n\log \log n)\)
积性函数 \(\times\) 积性函数 \(O(n)\)
如果我们能把每一个质数 \(p^a\) 的答案得到，我们就能欧拉筛出所有数的答案。
我们对于每个质数直接暴力即可，小于 \(\sqrt n\) 的质数复杂度是 \(O(\frac{\sqrt n}{\log \sqrt n}\log^2n) = O(\sqrt n\log n)\le O(n)\)，大于 \(\sqrt n\) 的每个质数只有一项，不涉及卷积的复杂度，所以总体是低于 \(O(n)\) 的。
标签：log,狄利克,卷积,质数,sqrt,times,积性,nlogn,函数 From： https://www.cnblogs.com/pp-orange/p/18220436