2020-2021:teams:hotpot:杜教筛
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:杜教筛 [2020/05/22 18:07] 喝西北风 |
2020-2021:teams:hotpot:杜教筛 [2020/05/22 18:22] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 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}})$ | ||
| + | |||
| + | ===推广=== | ||
| + | |||
| + | 这个问题的核心，是对于所求的$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> | <code/cpp> | ||
2020-2021/teams/hotpot/杜教筛.1590142031.txt.gz · 最后更改: 2020/05/22 18:07 由 喝西北风
