0 约定
\([n]=[1,n]\cap\mathtt Z\)
1 数论分块
形如 $S(n)=\sum\limits_{i=1}^nf(i)g(\left \lfloor \dfrac{n}{i} \right \rfloor) $。
可以在 \(O(\sqrt n)\) 的时间复杂度内求解。
1.1 解法
-
对于 \(1\le i\le \sqrt n\)，
显然，\(i\) 最多 \(\sqrt n\) 种取值，故而 \(\left \lfloor \dfrac{n}{i} \right \rfloor\) 最多有 \(\sqrt n\) 种取值。
-
对于 \(\sqrt n<i\le n\)，
有 \(\left \lfloor \dfrac{n}{i} \right \rfloor\le\sqrt n\)，最多亦有 \(\sqrt n\) 种取值。
综上，如果可以 \(O(1)\) 得到 \(f\) 的区间和，那么可以通过枚举 \(\left \lfloor \dfrac{n}{i} \right \rfloor\) 的取值，\(O(2\sqrt n)\approx O(\sqrt n)\) 求解。
具体代码如下：
int res = 0;
for (int i = 1, j; i <= n; i = j+1) {
j = n/(n/i);
res += (f(j) - f(i-1)) * g(n/i);
}
其中 \(j\) 为对于当前 \(i\) 满足 \(\left \lfloor \dfrac{n}{i} \right \rfloor=\left \lfloor \dfrac{n}{j} \right \rfloor\) 的最大的 \(j\)。
2 莫比乌斯函数
对于一些函数 \(f(n)\)，如果很难直接求出它的值，而容易求出其倍数和或约数和 \(g(n)\)，那么可以通过莫比乌斯反演，简化运算得到 \(f(n)\) 的值。
2.1 定义
定义莫比乌斯函数：
\[\mu(n)= \begin{cases} 1&n=1\\ 0&n\text{ 含有平方因子}\\ (-1)^k&k\text{ 为 }n\text{ 的不同质因子个数}\\ \end{cases}\]注：
- 「含有平方因子」是指存在 \(p\) 为质数，\(\alpha\) 为满足 \(p^{\alpha}=n\) 的最大整数，\(\alpha\ge2\)。eg. \(\mu(8)=0\)。
2.2 性质
-
\(\mu(n)\) 是 不完全 积性函数，即 \(\mu(x)\mu(y)=\mu(xy)\) 当且仅当 \((x,y)=1\)。
-
狄利克雷卷积 相关：
-
\((\mu*\text I)=\begin{cases} 1&n=1\\ 0&n\neq 1\\ \end{cases}\)
证明与下类似。
-
\((\mu*\text{Id})=\varphi\)
证明：
设：\(n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}\)，\(p\) 为质数，\(\alpha\) 为正整数。
\[\begin{aligned} (\mu*\text{Id})(n) &=\sum_{d|n}\mu(d)\dfrac n d\\ &\begin{array}{c} =\left(\mu(1)\frac{p_1^{\alpha_1}}{1}+\mu(p_1)\frac{p_1^{\alpha_1}}{p_1}+\cdots+\mu(p_1^{\alpha_1})\frac{p_1^{\alpha_1}}{p_1^{\alpha_1}}\right) \\ \hspace{1.5em}\vdots \\ \hspace{1.5em}\left(\mu(1)\frac{p_k^{\alpha_k}}{1}+\mu(p_k)\frac{p_k^{\alpha_k}}{p_k}+\cdots+\mu(p_k^{\alpha_k})\frac{p_k^{\alpha_k}}{p_k^{\alpha_k}}\right) \\ \end{array}&\text{【直接把括号展开，就可以发现她是对的】}\\ &=\left(p_1^{\alpha_1}-\frac{p_1^{\alpha_1}}{p_1}\right)\left(p_2^{\alpha_2}-\frac{p_2^{\alpha_2}}{p_2}\right)\cdots\left(p_k^{\alpha_k}-\frac{p_k^{\alpha_k}}{p_k}\right)&\text{【把 } \mu \text{ 的值带进去】}\\ &=\frac{(p_1-1)p_1^{\alpha_1}}{p_1}\times\frac{(p_2-1)p_2^{\alpha_2}}{p_2}\times\cdots\times\frac{(p_k-1)p_k^{\alpha_k}}{p_k}\\ &=(p_1-1)p_1^{\alpha_1-1}(p_2-1)p_2^{\alpha_2-1}\cdots(p_k-1)p_k^{\alpha_k-1}\\ &=\varphi(n)&\text{【 }\varphi\text{ 的一种公式计算法】} \end{aligned}\]
-
3 莫比乌斯反演
设一个数论函数 \(f(x)\)，和另一个数论函数 \(F(x)\) 表示 \(f\)
则有：
\[f(x)=\sum\limits_{i=1}^{\left\lfloor \frac n x\right\rfloor}\mu(i)F(ix) \]4 例题
4.1
感性感知一下，\(\gcd(i,j)\) 的取值实际上很少，所以突破口在于枚举她的取值。
设：
\(f(d)=\sum\limits_{i,j\in[n]\\\gcd(i,j)=d}ij\)
\(F(d)\)
\(G(x)=\sum\limits_{i=1}^ni=\dfrac{n(n+1)}2\)
答案即为 \(Ans=\sum\limits_{d=1}^nf(d)d\)。
下考虑求解 \(F(d)\)：
\[\begin{aligned}F(d)&=\sum_{d|i}\sum_{d|j}ij\\ &=\sum_{d|i}i\times\sum_{d|j}j\\ &=\left(\sum_{i=1}^{\left\lfloor\frac n i\right\rfloor}id\right)^2\\ &=\left(G\left(\left\lfloor\frac n i\right\rfloor\right) d\right)^2\\ \end{aligned}\]从而：
\[Ans=\sum\limits_{d=1}^nd\sum\limits_{i=1}^{\left\lfloor \frac n i\right\rfloor}\mu(i)F(ix) \]推柿子：
\[\begin{aligned}\sun\end{aligned} \]\[\] 标签：right,frac,乌斯,sum,mu,反演,莫比,alpha,left From： https://www.cnblogs.com/CloudWings/p/17985949