这是一种对于一个数论函数 \(f(n)\)，计算 \(S(n)=\sum_{i=1}^n f(i)\) 的快速方法。
构造两个积性函数 \(h,g\) 满足 \(h=g*f\)，根据卷积的定义，有 \(h(i)=\sum_{d|i}g(d)f(\frac{i}{d})\)，对 \(h\) 求和，有：
\[\sum_{i=1}^n h(i)=\sum_{i=1}^n\sum_{d|i}g(d)f(\frac{i}{d}) \]\[=\sum_{d=1}^n g(d)\sum_{d|i}^n f(\frac{i}{d})=\sum_{d=1}^ng(d)\sum_{i=1}^{n/d}f(i)=\sum_{d=1}^n g(d)S(⌊\frac{n}{d}⌋) \]然后我们得到
\[\sum_{i=1}^nh(i)=g(1)S(n)+\sum_{d=2}^n g(d)S(⌊\frac{n}{d}⌋) \]\[g(1)S(n)=\sum_{i=1}^nh(i)-\sum_{d=2}^n g(d)S(⌊\frac{n}{d}⌋) \]\[g(1)S(n)=\sum_{i=1}^nh(i)-\sum_{i=2}^n g(i)S(⌊\frac{n}{i}⌋) \]记忆化之后复杂度是 \(O(n^{\frac{3}{4}})\) 的捏。
如果预处理 \(S(1,...,k)\)，那么复杂度 \(O(k)+O(\frac{n}{\sqrt k})\) 的捏。
当 \(k=n^{\frac{2}{3}}\) 时候有最小值 \(O(n^{\frac{2}{3}})\) 的捏。
欧拉函数怎么独角骰？欧拉函数怎么独角骰？欧拉函数怎么独角骰？
首先有一个 \(n=\sum_{d|n}\phi(d)\)，然后套用上面的柿子 \(g(1)S(n)=\sum_{i=1}^nh(i)-\sum_{i=2}^n g(i)S(⌊\frac{n}{i}⌋)\) 可得：
\[S(n)=\frac{n(n+1)}{2}-\sum_{i=2}^n S(⌊\frac{n}{i}⌋) \]梅比乌斯怎么独角晒？梅比乌斯怎么独角晒？梅比乌斯怎么独角晒？
首先有一个 \([n=1]=\sum_{d|n}\mu(d)\)，还是套用上面的柿子可得：
\[S(n)=1-\sum_{i=2}^nS(⌊\frac{n}{i}⌋) \] 标签：nh,frac,函数,sum,杜教,独角,梅比 From： https://www.cnblogs.com/chelsyqwq/p/18111463