2020-2021:teams:farmer_john:莫比乌斯反演技巧总结
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:莫比乌斯反演技巧总结 [2020/08/21 17:29] jjleo |
2020-2021:teams:farmer_john:莫比乌斯反演技巧总结 [2020/08/21 17:35] (当前版本) jjleo [将乘积的欧拉函数展开] |
||
|---|---|---|---|
| 行 17: | 行 17: | ||
| =====常用结论===== | =====常用结论===== | ||
| - | ====1==== | + | ====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}$$ | $$\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}$$ | ||
| - | ====2=== | + | ====将乘积的欧拉函数展开=== |
| - | $$\varphi$$ | + | $$\varphi(nm)=\frac{\varphi(n)\varphi(m)\gcd(n,m)}{\varphi(\gcd(n,m))}$$ 只需将欧拉函数展开，提取出$n$与$m$的公共质因子即可证明。 |
2020-2021/teams/farmer_john/莫比乌斯反演技巧总结.1598002152.txt.gz · 最后更改: 2020/08/21 17:29 由 jjleo
