差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:farmer_john:莫比乌斯反演技巧总结 [2020/08/14 16:11]
jjleo [常用套路]
+++ 2020-2021:teams:farmer_john:莫比乌斯反演技巧总结 [2020/08/21 17:35] (当前版本)
jjleo [将乘积的欧拉函数展开]
@@ 行 9: / 行 9: @@
 =====常用套路=====
-  * 求 $$\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)$$ 先枚举$d = \gcd(i,j)$，再套用$\epsilon = \mu * 1$  $$=\sum_{d=1}^{n}d\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{d} \right\rfloor}[\gcd(i,j)=1]$$ $$=\sum_{d=1}^{n}d\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{d} \right\rfloor}\sum_{p|\gcd(i,j)}\mu(p)$$ 再枚举$p$ $$=\sum_{d=1}^{n}d\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\mu(p)\sum_{i=1}^{\left\lfloor \frac{n}{dp} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{dp} \right\rfloor}1$$ $$=\sum_{d=1}^{n}d\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\mu(p)\frac{\left\lfloor \frac{n}{dp} \right\rfloor(\left\lfloor \frac{n}{dp} \right\rfloor + 1)\left\lfloor \frac{m}{dp} \right\rfloor(\left\lfloor \frac{m}{dp} \right\rfloor + 1)}{4}$$ 设$T=dp$，枚举$T$  $$=\sum_{T=1}^{n} \frac{\left\lfloor \frac{n}{T} \right\rfloor(\left\lfloor \frac{n}{T} \right\rfloor + 1)\left\lfloor \frac{m}{T} \right\rfloor(\left\lfloor \frac{m}{T} \right\rfloor + 1)}{4}\sum_{d|T}d\mu(\frac{T}{d})$$ 套用$\varphi= \mu * \operatorname{id}$ $$=\sum_{T=1}^{n} \frac{\left\lfloor \frac{n}{T} \right\rfloor(\left\lfloor \frac{n}{T} \right\rfloor + 1)\left\lfloor \frac{m}{T} \right\rfloor(\left\lfloor \frac{m}{T} \right\rfloor + 1)}{4}\varphi(T)$$ 求出欧拉函数前缀和，直接整除分块即可。
+====经典老番====
-  * 上述过程中最为关键的是设$T=dp$，枚举$T$这一步。该操作可以概括为如下等式：$$\sum_{d=1}^{n}f(d)\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor}g(p)h(dp)=\sum_{T=1}^{n}h(T)\sum_{d|T}f(d)g(\frac{T}{d})$$设$F(n)=\sum_{d|n}f(d)g(\frac{n}{d})$，则原式可化为$$\sum_{T=1}^{n}h(T)F(T)$$如果两个函数一个可以整除分块，另一个可以在合理时限内求出前缀和，那么就可以以较低时间复杂度求出答案。
+求 $$\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)$$ 先枚举$d = \gcd(i,j)$，再套用$\epsilon = \mu * 1$  $$=\sum_{d=1}^{n}d\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{d} \right\rfloor}[\gcd(i,j)=1]$$ $$=\sum_{d=1}^{n}d\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{d} \right\rfloor}\sum_{p|\gcd(i,j)}\mu(p)$$ 再枚举$p$ $$=\sum_{d=1}^{n}d\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\mu(p)\sum_{i=1}^{\left\lfloor \frac{n}{dp} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{m}{dp} \right\rfloor}1$$ $$=\sum_{d=1}^{n}d\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\mu(p)\frac{\left\lfloor \frac{n}{dp} \right\rfloor(\left\lfloor \frac{n}{dp} \right\rfloor + 1)\left\lfloor \frac{m}{dp} \right\rfloor(\left\lfloor \frac{m}{dp} \right\rfloor + 1)}{4}$$ 设$T=dp$，枚举$T$  $$=\sum_{T=1}^{n} \frac{\left\lfloor \frac{n}{T} \right\rfloor(\left\lfloor \frac{n}{T} \right\rfloor + 1)\left\lfloor \frac{m}{T} \right\rfloor(\left\lfloor \frac{m}{T} \right\rfloor + 1)}{4}\sum_{d|T}d\mu(\frac{T}{d})$$ 套用$\varphi= \mu * \operatorname{id}$ $$=\sum_{T=1}^{n} \frac{\left\lfloor \frac{n}{T} \right\rfloor(\left\lfloor \frac{n}{T} \right\rfloor + 1)\left\lfloor \frac{m}{T} \right\rfloor(\left\lfloor \frac{m}{T} \right\rfloor + 1)}{4}\varphi(T)$$ 求出欧拉函数前缀和，直接整除分块即可。
-  * 结论：$$\sum_{i=1}^ni[\gcd(i,n)=1]=\frac{n\varphi(n)+[n==1]}{2}$$
+上述过程中最为关键的是设$T=dp$，枚举$T$这一步。该操作可以概括为如下等式：$$\sum_{d=1}^{n}f(d)\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor}g(p)h(dp)=\sum_{T=1}^{n}h(T)\sum_{d|T}f(d)g(\frac{T}{d})$$设$F(n)=\sum_{d|n}f(d)g(\frac{n}{d})$，则原式可化为$$\sum_{T=1}^{n}h(T)F(T)$$如果两个函数一个可以整除分块，另一个可以用$O(1)/O(n \log n)/O(n)/O(n^{\frac{2}{3}})$求出前缀和，那么就可以以较低时间复杂度求出答案。
+=====常用结论=====
+====1到n中与n互质的数之和====
+$$\sum_{i=1}^ni[\gcd(i,n)=1]=\frac{n\varphi(n)+[n=1]}{2}$$ 证明如下：$$\sum_{i=1}^ni[\gcd(i,n)=1]$$ 套用$\epsilon = \mu * 1$ $$=\sum_{i=1}^ni\sum_{d|\gcd(i,n)}\mu(d)$$ 枚举$d$，注意这里$n$是已知量，只需枚举$d|n$ $$=\sum_{d|n}\mu(d)d\sum_{i=1}^{\frac{n}{d}}i$$ $$=\frac{1}{2}\sum_{d|n}\mu(d)d\frac{n}{d} ( \frac{n}{d} + 1)$$ $$=\frac{n}{2}\sum_{d|n}\mu(d)( \frac{n}{d}  + 1)$$ $$=\frac{n}{2}(\sum_{d|n}\mu(d)\frac{n}{d}+\sum_{d|n}\mu(d))$$ 由$\varphi= \mu * \operatorname{id}$和$\epsilon = \mu * 1$可得$$=\frac{n}{2}(\varphi(n)+[n=1])$$ $$=\frac{n\varphi(n)+n[n=1]}{2}$$ $$=\frac{n\varphi(n)+[n=1]}{2}$$
+====将乘积的欧拉函数展开===
+$$\varphi(nm)=\frac{\varphi(n)\varphi(m)\gcd(n,m)}{\varphi(\gcd(n,m))}$$ 只需将欧拉函数展开，提取出$n$与$m$的公共质因子即可证明。

CVBB ACM Team

用户工具

站点工具

差别

页面工具