2020-2021:teams:hotpot:杜教筛
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:杜教筛 [2020/05/22 18:06] 喝西北风 |
2020-2021:teams:hotpot:杜教筛 [2020/05/22 18:22] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====问题描述（洛谷4213）==== | ====问题描述（洛谷4213）==== | ||
| - | 给定N($N<2^{31}$)，求1到N的欧拉函数和莫比乌斯函数之和 | + | 给定$N(N<2^{31}$)，求1到N的欧拉函数和莫比乌斯函数之和 |
| ====解决方法==== | ====解决方法==== | ||
| 行 32: | 行 32: | ||
| 先线性求出$10^7$以内的$S(n),T(n)$，对于大于$10^7$的$S(n),T(n)$，可通过数论分块递归计算出。 | 先线性求出$10^7$以内的$S(n),T(n)$，对于大于$10^7$的$S(n),T(n)$，可通过数论分块递归计算出。 | ||
| + | |||
| + | ====问题分析==== | ||
| + | |||
| + | ===时间复杂度=== | ||
| 可以证明，杜教筛的时间复杂度为$O(n^{\frac{3}{4}})$ | 可以证明，杜教筛的时间复杂度为$O(n^{\frac{3}{4}})$ | ||
| - | <code\cpp> | + | ===推广=== |
| + | |||
| + | 这个问题的核心，是对于所求的$g(n)$，需要找到一个合适的$f(n)$，使得$\sum_{i=1}^n(f*g)(i)$能被快速计算出。 | ||
| + | |||
| + | 可以尝试计算$\sum_{i=1}^n i\phi (i)$。提示：设$f(n)=n$。$(f*g)(n)=n^2$ | ||
| + | |||
| + | <code/cpp> | ||
| #include<iostream> | #include<iostream> | ||
| #include<cstdio> | #include<cstdio> | ||
| 行 114: | 行 124: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | <\code> | + | </code> |
2020-2021/teams/hotpot/杜教筛.1590142007.txt.gz · 最后更改: 2020/05/22 18:06 由 喝西北风
