Cy 筛
给定 \(f,g\) 和一个系数 \(T,n\), 我们知道 \([1,T]\) 和 \(\{\frac ni|i\in[1,\lfloor\frac nT\rfloor]\}\) 总共 \(T+\lfloor\frac nT\rfloor\) 个下标对应的 \(F=\sum f,G=\sum g\), 而我们要求出 \(H=\sum h=\sum f*g\) 在这些下标上的取值.
我们发现这个东西有点像杜教筛, 所以考虑用类似于杜教筛的数论分块来做.
\(1.i\in[1,T]\)
我们可以通过差分求出 \(f,g\), 然后暴力卷积求得 \(h\), 再做前缀和得到 \(H\).
这里的复杂度为 \(O(T\log T)\).
\(2.i\in\{\frac ni|i\in[1,\lfloor\frac nT\rfloor]\}\)
先回到定义式上.
- \(H(n)=\sum\limits_{
- i=1
- }^n\sum\limits_{
- d|n
- }g(d)f(\frac{
- i
- }{
- d
- })\)
- \(H(n)=\sum\limits_{
- d=1
- }^ng(d) \sum\limits_{
- i=1
- }^{
- \lfloor\frac{
- n
- }{
- d
- }\rfloor
- }f(i)\)
我们画一个 \(y=\frac nx\) 的反比例函数的图像出来.
每个整点 \((x,y)\) 有一个权值 \(f(x)g(y)\).
\(H(n)\) 就等价于 \(y=\frac nx\) 下整点的权值和.
我们考虑先分别求出 \(x\le\sqrt n\) 的所有整点的权值和和 \(y\le\sqrt n\) 的所有整点的权值和.
分别为 \(\sum\limits_{i=1}^{\lfloor\sqrt n\rfloor}f(i)G(\lfloor\frac ni\rfloor)\) 和 \(\sum\limits_{i=1}^{\lfloor\sqrt n\rfloor}g(i)F(\lfloor\frac ni\rfloor)\).
然后我们可以发现 \(x,y\le\sqrt n\) 的部分被算了两次, 这部分的权值和为 \(F(\lfloor\sqrt n\rfloor)G(\lfloor\sqrt n\rfloor)\), 减掉就好了.
这样对于每个 \(i\), 我们都可以用 \(\sqrt i\) 的复杂度计算出 \(H(i)\).
这部分总的复杂度为 \(\sum\limits_{i=1}^{\lfloor\frac nT\rfloor}O(\sqrt{\frac ni})=O(\frac n{\sqrt T})\).
总复杂度为 \(O(T\log T+\frac n{\sqrt T})\), 当 \(T=n^{0.6\sim0.65}\) 时可以获得很不错的复杂度.
Fibonacci 循环节
My Link
基础? 数论
来源: http://www.bubuko.com/infodetail-3353627.html