杜教筛&min_25筛复习
杜教筛
适用条件
-
你要能构造出(g(x),h(x))，使得(h=f*g)。
-
(G(x),H(x))的值可以快速计算。
过程
我们要求的是(F(n)=sum_{i=1}^{n}f(i))，现在有(h=f*g)，(G(x),H(x))分别为(g(x),h(x))的前缀和。
[egin{aligned}
H(n)=&sum_{i=1}^{n}h(i)\
=&sum_{i=1}^{n}sum_{d|i}f(frac{i}{d})g(d)\
=&sum_{d=1}^{n}g(d)sum_{i=1}^{lfloor frac{n}{d}
floor}f(i)\
=&sum_{d=1}^{n}g(d)F(lfloor frac{n}{d}
floor)\
g(1)F(n)=H(n)-&sum_{d=2}^{n}g(d)F(lfloor frac{n}{d}
floor)
end{aligned}
]
通过线性筛预处理出前(n^{frac{2}{3}})的前缀和，加上记忆化，可以做到(O(n^{frac{2}{3}}))的时间复杂度。
min_25筛
适用条件
-
(f(P))的值是一个关于(P)的多项式。
-
(f(P^Q))的值可以快速计算。
-
当然，(f(x))必须是一个积性函数。
原理
先咕了，咕咕咕。
第一次处理
假设(f'(x)=x^k)，令(g[P_i][x])表示所有(f'(y))的和，其中(1 leq y leq x)，(y)是质数或者(y)的最小质因子大于(P_i)，有这样的递推式：
[g[P_i][x]=g[P_{i-1}][x]-f'(P_i)(g[P_{i-1}][lfloorfrac{x}{P_i}
floor]-sum_{j=1}^{i-1}f'(P_j)), x geq P_i^2
]
[g[P_i][x]=g[P_{i-1}][x], x < P_i^2
]
(g[P_i][x])的第一维可以使用滚动数组优化掉，时间复杂度为(O(frac{n^{frac{3}{4}}}{log n}))。
第二次处理
为了方便，这里使用(g[x])表示(g[P_{cnt}][x])（(cnt)表示质数个数）。
令(S(x,P_i))表示所有(f(y))的和，其中(1 leq y leq x)，(y)的最小质因子大于等于(P_i)，有：
[S(x,P_i)=g[x]-sum_{j=1}^{i-1}f(P_j)+sum_{j=i}^{P_j^2 leq x}sum_{k=1}^{P_j^{k+1} leq x}f(P_j^k)S(lfloorfrac{x}{p_j^k}
floor,P_{j+1})+f(P_j^{k+1})
]
这里无需记忆化，直接递归计算即可，时间复杂度为(O(frac{n^{frac{3}{4}}}{log n}))。