关于积性函数前缀和的一些胡扯
想出一道不一般的积性函数前缀和的题，题没出出来，倒是发现不少有意思的东西。
一些定义
有些定义是我胡扯的。
对于积性函数 \(f\) ，称其特征函数 \(F\) 为 \(f\) 关于质数 \(p\) 的函数，准确来说 \(F\) 是 \(f\) 的特征函数当且仅当对于任意质数 \(p\) 有 \(F(p) = f(p)\) ，可以发现 \(F\) 并不是唯一的，但是我们只考虑最简单的那个，例如对于任意质数 \(p\) 有 \(f(p) = p + 1\) ，不妨令任意 \(x\) 有 \(F(x) = x + 1\) ，可以发现 \(F\) 并不一定是积性函数。
记积性函数 \(I_m(x) = x^m\) 。
对于数论函数 \(f\) ，其前缀和函数记为 \(S_f\) ，满足 \(S_f(n) = \sum_{i=1}^n f(i)\) 。
记 \(B(n) = \lfloor \sqrt{n} \rfloor\) ，\(n / i = \lfloor \frac{n}{i} \rfloor\) 。
关于特征函数
两个积性函数相乘（狄利克雷卷积），它们的特征函数相加（线性相加）。
Powerful Number
众所周知 Powerful Number 可以快速求一类积性函数前缀和，这玩意的本质是什么呢？
对于积性函数 \(f\) ，称其为 Powerful Function ，当且仅当其有特征函数 \(F\) 恒为 0 。
- 定理 1 ：Powerful Function 在 \(n\) 以内的非零的值只有 \(O(\sqrt{n})\) 个。
那么 Powerful Number 求 \(S_f(n)\) 的本质就是找一个与 \(f\) 特征函数相同的数论函数 \(h\) ，然后令 \(g = f \times h^{-1}\) ，可以知道 \(g\) 特征函数是两者相减，那么 \(g\) 一定是 Powerful Function ，于是根据
\[S_f(n) = \sum_{i=1}^n g(i) S_h(\lfloor \frac{n}{i} \rfloor)\]
枚举 \(g\) 的有效值，也就是 Powerful Number ，问题可以从求 \(S_f\) 转换为求 \(S_h\) 。
如果 \(S_h(n)\) 可以 \(O(1)\) 求，那么 \(S_f(n)\) 就可以 \(O(\sqrt{n})\) 求，但大多数时候并非如此。
卷积构造
卷积构造也是求积性函数前缀和的利器，杜教筛便是广为人知的一个例子。
构造狄利克雷卷积 \(f \times g = h\) ，那么根据
\[S_f(n) = S_h(n) - S_g(n) + S_f(B(n)) S_g(B(n)) - \sum_{i=2}^{B(n)} (g(i) S_f(n / i) + f(i) S_g(n / i))\]
即可把求 \(S_f(n)\) 的问题转换为求 \(S_g, S_h\) 。
事实上，把上式换个方向，构造卷积 \(f = g \times h\) ，根据
\[S_f(n) = \sum_{i=1}^{B(n)} (g(i) S_f(n / i) + f(i) S_g(n / i)) - S_f(B(n)) S_g(B(n))\]
也同样可以把求 \(S_f(n)\) 的问题转换为求 \(S_g, S_h\) 。
回到 Powerful Number
有时候找不到特征函数相同的可以 \(O(1)\) 求前缀和的数论函数，但是可以把特征函数拆成两部分的和，然后两部分分别可以找到对应可以 \(O(1)\) 求的数论函数，这时候也是可以用 Powerful Number 去算的。
也就是构造卷积 \(h = a \times b\) ，如果 \(S_a, S_b\) 都可以 \(O(1)\) 求值，那么根据上文的卷积构造的式子，就可以 \(O(\sqrt{n})\) 求出 \(S_h(n)\) ，这时候对于任意与 \(h\) 特征函数相同的 \(f\) ，都可以利用 Powerful Number 来 \(O(\sqrt{n}\log{n})\) 求出 \(S_f(n)\) 。
注意到对于任意常数 \(m\) ，\(I_m\) 都是可以 \(O(1)\) 求值的，那么只要 \(f\) 的特征函数可以表示为恰好两个形如 \(x^k\) 的单项式的和，\(S_f\) 就是可以 \(O(\sqrt{n}\log{n})\) 求的。
例如 \(f(p) = 2, f(p) = p + 1, f(p) = p^5 + p^3\) 等。
由于上文构造卷积两个方向都可行，那么如果 \(f\) 的特征函数可以表示为恰好两个形如 \(x^k\) 的单项式的差，是否可以以同样复杂度求前缀和呢？
很遗憾答案（似乎）是否定的，因为另一个方向（杜教筛的方向）需要递归用到自身的函数值。不过虽然没法做到 \(O(\sqrt{n}\log{n})\) ，用杜教筛的 trick 可以把这类问题都做到 \(O(n^{\frac{2}{3}})\) 。
这里顺便可以思考思考，为什么约数个数函数，约数和函数有 \(O(\sqrt{n})\) 算前缀和的公式？本质上就是因为约数个数函数是 \(I_0 \times I_0\) ，约数和函数是 \(I_0 \times I_1\) ，两者的特征函数分别是 \(1 + 1\) 和 \(x + 1\) 。
更一般的情况
如果 \(f\) 的特征函数可以是一个多项式，如何求 \(S_f(n)\) ？
多项式可以拆成若干单项式的和，单项式可以拆成若干系数为 \(1\) 的单项式的和，也就是说这样的 \(f\) 总可以找到对应的 \(h\) 表示为若干 \(I_m\) 的狄利克雷卷积。
例如 \(f(p) = 3p^3 + p^2 - p + 1\) ，那么设 \(h = I_3 \times I_3 \times I_3 \times I_2 \times I_1^{-1} \times I_0\) ，不难发现逐个合并可以以 \(O(n^{\frac{2}{3}})\) 的复杂度算出所有 \(S_h(n/i)\) ，然后用 Powerful Number 的做法可以 \(O(\sqrt{n})\) 求 \(S_f(n)\) ，也可以 \(O(n^{\frac{2}{3}})\) 求出所有 \(S_f(n/i)\) 。
如果系数更大，比如 \(f(p) = K p\) ，那么设 \(h = I_1^K\) ，快速幂合并，可以以 \(O(n^{\frac{2}{3}}\log{K})\) 的复杂度求出所有 \(S_f(n/i)\) 。
更一般的结论就不难导出了，如果 \(f\) 的特征函数可以是一个多项式，可以以 \(O(Ln^{\frac{2}{3}}\log)\) 的复杂度求出所有 \(S_f(n/i)\) ，其中 \(L\) 是多项式的次数。
min25 筛
众所周知的是，如果 \(f\) 的特征函数可以是一个多项式，min25 筛也可以求 \(S_f(n)\) ，虽然复杂度是 \(O(n^{1-\epsilon}+Ln^{\frac{3}{4}}/\log)\) 但是实际运用非常优秀。
所以上述做法在实际运用中并不理想，这也是我没能出出一道题目的原因，除非 \(n\) 开到特别大放到天河一号上面跑，否则上述做法的实际运行效率就不会优于 min25 筛。
但是上述做法的复杂度确实更优秀，或许可以为这类问题的理论研究提供一定的思路。
有意思的是，这两种做法的思路和方向虽然截然不同，但它们都只关注积性函数的特征函数，这或许能带来一些启发。
End
本文尽是一些胡扯，主要是为自己突发的灵感记个笔记，如有错误的地方还请指正。
可惜的是这个做法在实际应用中没啥用，但是我目前没有进一步的优化思路，如有想法欢迎讨论。
update: 不光是常数，在复杂度上也没用，改进后的 min25 筛可以以 \(O(n^{\frac{2}{3}})\) 的复杂度处理同样范围的问题。