基础？数论

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

基础？数论

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12110773.html