2020-2021:teams:farmer_john:莫比乌斯反演技巧总结
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:莫比乌斯反演技巧总结 [2020/08/21 17:28] jjleo [结论] |
2020-2021:teams:farmer_john:莫比乌斯反演技巧总结 [2020/08/21 17:35] (当前版本) jjleo [将乘积的欧拉函数展开] |
||
|---|---|---|---|
| 行 15: | 行 15: | ||
| 上述过程中最为关键的是设$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}})$求出前缀和，那么就可以以较低时间复杂度求出答案。 | 上述过程中最为关键的是设$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==== | + | =====常用结论===== |
| + | |||
| + | ====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}$$ | ||
| - | ====结论==== | + | ====将乘积的欧拉函数展开=== |
| - | $$\varphi$$ | + | $$\varphi(nm)=\frac{\varphi(n)\varphi(m)\gcd(n,m)}{\varphi(\gcd(n,m))}$$ 只需将欧拉函数展开，提取出$n$与$m$的公共质因子即可证明。 |
2020-2021/teams/farmer_john/莫比乌斯反演技巧总结.1598002109.txt.gz · 最后更改: 2020/08/21 17:28 由 jjleo
