杜教筛学习笔记

我们现在需要求一个函数f ff的前缀和S ( n ) ∑ i 1 n f ( i ) S(n)\sum_{i1}^nf(i)S(n)∑i1n​f(i)。设h ( n ) ∑ d ∣ n g ( d ) f ( n d ) h(n)\sum_{d\mid n}g_(d)f(\frac nd)h(n)∑d∣n​g(​d)f(dn​)即h ( n ) ( f ∗ g ) ( n ) h(n)(f*g)(n)h(n)(f∗g)(n)。那么有∑ i 1 n h ( i ) ∑ i 1 n ∑ d ∣ i g ( d ) f ( i d ) ∑ d 1 n g ( d ) ∑ i 1 ⌊ n d ⌋ f ( i ) ∑ d 1 n g ( d ) S ( ⌊ n d ⌋ ) g ( 1 ) S ( n ) ∑ d 2 n g ( d ) S ( ⌊ n d ⌋ ) S ( n ) ∑ i 1 n h ( i ) − ∑ d 2 n g ( d ) S ( ⌊ n d ⌋ ) g ( 1 ) \begin{align*} \sum_{i1}^nh(i)\sum_{i1}^n\sum_{d\mid i}g(d)f(\frac id)\\ \sum_{d1}^ng(d)\sum_{i1}^{\lfloor\frac nd\rfloor}f(i)\\ \sum_{d1}^ng(d)S(\lfloor\frac nd\rfloor)\\ g(1)S(n)\sum_{d2}^ng(d)S(\lfloor\frac nd\rfloor)\\ S(n)\frac{\sum_{i1}^nh(i)-\sum_{d2}^ng(d)S(\lfloor\frac nd\rfloor)}{g(1)} \end{align*}i1∑n​h(i)S(n)​i1∑n​d∣i∑​g(d)f(di​)d1∑n​g(d)i1∑⌊dn​⌋​f(i)d1∑n​g(d)S(⌊dn​⌋)g(1)S(n)d2∑n​g(d)S(⌊dn​⌋)g(1)∑i1n​h(i)−∑d2n​g(d)S(⌊dn​⌋)​​设一个阈值N NN当n N nNnN时预处理出答案其祂情况用上面的式子计算。其中∑ d 2 n g ( d ) S ( ⌊ n d ⌋ ) \sum_{d2}^ng(d)S(\lfloor\frac nd\rfloor)∑d2n​g(d)S(⌊dn​⌋)可以用整除分块优化并递归计算所有S ( ⌊ n d ⌋ ) S(\lfloor\frac nd\rfloor)S(⌊dn​⌋)。如果我们能选取适当的h hh和g gg使得能快速求出h hh和g gg的前缀和那么问题就解决了。经测算当N NN取到m a x n 2 3 maxn^{\frac23}maxn32​时时间复杂度取到最优为O ( n 2 3 ) \mathcal O(n^{\frac23})O(n32​)。求μ \muμ的前缀和。很多时候要计算的f ff为莫比乌斯函数μ \muμ此时取h ( n ) [ n 1 ] h(n)[n1]h(n)[n1]中括号是艾弗森括号g ( n ) 1 g(n)1g(n)1由于[ n 1 ] ∑ d ∣ n μ ( d ) [n1]\sum_{d\mid n}\mu(d)[n1]∑d∣n​μ(d)所以h ( n ) ∑ d ∣ n g ( d ) f ( n d ) h(n)\sum_{d\mid n}g(d)f(\frac nd)h(n)∑d∣n​g(d)f(dn​)而且h , g h,gh,g的前缀和都易于计算。例题P3172 [CQOI2015] 选数题解