贾志鹏线性筛

线性筛法与积性函数南京外国语学校贾志鹏Eratosthenes筛法（埃拉托斯特尼筛法）时间复杂度：O(𝑁loglog𝑁)空间复杂度：O(𝑁)Euler筛法（欧拉筛法）每个合数只会被它最小的质因数筛去，因此时间复杂度为O(𝑁)时间复杂度证明设合数𝑛最小的质因数为𝑝，它的另一个大于𝑝的质因数为𝑝′，令𝑛=𝑝𝑚=𝑝′𝑚′。观察上面的程序片段，可以发现𝑗循环到质因数𝑝时合数𝑛第一次被标记（若循环到𝑝之前已经跳出循环，说明𝑛有更小的质因数），若也被𝑝′标记，则是在这之前（因为𝑚′𝑚），考虑𝑖循环到𝑚′，注意到𝑛=𝑝𝑚=𝑝′𝑚′且𝑝,𝑝′为不同的质数，因此𝑝|𝑚′，所以当𝑗循环到质数𝑝后结束，不会循环到𝑝′，这就说明不会被𝑝′筛去。积性函数考虑一个定义域为ℕ+的函数𝑓，对于任意两个互质的正整数𝑎,𝑏，均满足𝑓𝑎𝑏=𝑓𝑎𝑓(𝑏)，则函数𝑓被称为积性函数。假如对于任意两个正整数𝑎,𝑏，都有𝑓𝑎𝑏=𝑓𝑎𝑓(𝑏)，函数𝑓也被称为完全积性函数。容易看出，对于任意积性函数（完全积性函数），𝑓(1)=1。考虑一个大于1的正整数𝑁，设𝑁=𝑝𝑖𝛼𝑖，其中𝑝𝑖为互不相同的质数，那么对于一个积性函数𝑓，𝑓𝑁=𝑓𝑝𝑖𝛼𝑖=𝑓(𝑝𝑖𝛼𝑖)，如果𝑓还满足完全积性，则𝑓𝑁=𝑓𝑝𝑖𝛼𝑖常见积性函数欧拉函数𝜑𝜑(𝑛)表示1…𝑛中与𝑛互质的整数个数。结合中国剩余定理，容易证明𝜑(𝑛)为积性函数，但不是完全积性函数考虑一个质数𝑝和正整数𝑘，不难看出𝜑𝑝𝑘=𝑝𝑘−𝑝𝑘−1=𝑝−1𝑝𝑘−1欧拉定理：𝑎𝜑𝑛≡1(mod𝑛)，要求𝑎和𝑛互质。特例是费尔马小定理。可以利用这个定理求模意义下的乘法逆元：𝑎−1≡𝑎𝜑𝑛−1(mod𝑛)。𝜑(𝑑)𝑑|𝑛=𝑛当𝑛1时，1…𝑛中与𝑛互质的整数和为𝑛𝜑𝑛2莫比乌斯函数𝜇积性函数性质若𝑓𝑛,𝑔(𝑛)均为积性函数，则函数ℎ𝑛=𝑓𝑛𝑔(𝑛)也是积性函数。若𝑓𝑛为积性函数，则函数𝑔𝑛=𝑓(𝑑)𝑑|𝑛也是积性函数，反之亦然。莫比乌斯反演公式：𝑓𝑛=𝜇𝑑𝑔(𝑛𝑑)𝑑|𝑛莫比乌斯函数𝜇𝜇𝑛=1𝑛=1−1𝑘𝑛=𝑝1𝑝2⋯𝑝𝑘0其余情况𝜇(𝑑)𝑑|𝑛=[𝑛=1]莫比乌斯反演与容斥原理设𝑓𝑛=𝜑(𝑑)𝑑|𝑛，由前面的结论可知𝑓𝑛=𝑛，又𝜑𝑛=𝜇𝑑𝑓(𝑛𝑑)𝑑|𝑛，因此𝜑𝑛=𝜇𝑑𝑛𝑑𝑑|𝑛我们从另一个角度来理解一下𝜑𝑛=𝜇𝑑𝑛𝑑𝑑|𝑛。考虑不超过𝑛的正整数𝑘，根据欧拉函数的定义，我们要算出有多少𝑘与𝑛互质。令gcd𝑛,𝑘=𝑑，当𝑑1要被去除，考虑质数集合𝑃={2,3,5,7,11,13,…}，𝑑1时显然会是𝑃中某些质数的倍数。若𝑝|𝑑，可知满足这样条件的𝑘有𝑛𝑝个。这些是需要去掉的，但很容易发现中间有重复。莫比乌斯反演与容斥原理继续考虑两个不同质数𝑝1,𝑝2，若𝑝1𝑝2|𝑑，则这样的𝑑被重复去掉两次，需要加上𝑛𝑝1𝑝2。接着考虑三个不同质数𝑝1,𝑝2,𝑝3，若𝑝1𝑝2𝑝3|𝑑，在开始时被去掉三次，但是前面考虑两个质数时又被加回三次，因此需要再去掉𝑛𝑝1𝑝2𝑝3。这样的话，考虑𝑡个不同的质数𝑝1,𝑝2,𝑝3,…,𝑝𝑡，若𝑝1𝑝2𝑝3…𝑝𝑡|𝑑，根据容斥原理，需要加上−1𝑡𝑛𝑝1𝑝2𝑝3…𝑝𝑡。最后观察莫比乌斯函数定义和𝜑𝑛=𝜇𝑑𝑛𝑑𝑑|𝑛，可以发现𝑑其实就表示若干不同质数的乘积（若不是这样的，𝜇𝑑=0）。线性筛法求解积性函数积性函数的关键是如何求𝑓𝑝𝑘。观察线性筛法中的步骤，筛掉𝑛的同时还得到了它最小的质因数𝑝，我们希望能够知道𝑝在𝑛中的次数，这样就能利用𝑓𝑛=𝑓𝑝𝑘𝑓𝑛𝑝𝑘求出𝑓𝑛。令𝑛=𝑝𝑚，由于𝑝是𝑛最小的质因数，若𝑝2|𝑛，则𝑝|𝑚，并且𝑝也是𝑚最小的质因数。这样在进行筛法的同时，记录每个合数最小质因数的次数，就能算出新筛去合数最小质因数的次数。线性筛法求解积性函数但是这样还不够，我们还要能够快速求𝑓𝑝𝑘，这时一般就要结合𝑓函数的性质考虑。例如欧拉函数𝜑，𝜑𝑝𝑘=𝑝−1𝑝𝑘−1，因此进行筛法时，如果𝑝|𝑚，就乘上𝑝，否则乘上𝑝−1。再比如莫比乌斯函数𝜇，只有当𝑘=1时𝜇𝑝𝑘=−1，否则𝜇𝑝𝑘=0，和欧拉函数一样根据𝑚是否被𝑝整除进行判断。线性筛法求解积性函数（欧拉函数）线性筛法求解积性函数（莫比乌斯函数）线性筛法求逆元设𝑓𝑛为模大质数𝑃意义下𝑛的乘法逆元，现在要求出𝑓1,𝑓2,…,𝑓(𝑁)。很容易看出𝑓是完全积性函数，这样如果对于质数𝑝求出了𝑓(𝑝)的值，任意𝑓(𝑛)就能求出了。用扩展欧几里得算法求一次乘法逆元的时间复杂度为O(log𝑁)，而质数的个数正好为O𝑁log𝑁，因此整个算法的时间复杂度为O(𝑁)。其实呢，这个问题没这么烦。。设𝑃=𝑛𝑡+𝑘，则𝑓𝑛=𝑛𝑡2𝑓𝑘2mod𝑃𝑛𝑡≡−𝑘(mod𝑃)𝑛𝑡𝑓𝑘≡−1(mod𝑃)𝑛2𝑡2𝑓𝑘2≡1(mod𝑃)𝑛−1≡𝑛𝑡2𝑓𝑘2(mod𝑃)由于1≤𝑘𝑛，直接顺推求𝑓函数刚才解决的问题有什么用？考虑求𝑛𝑚mod𝑃，其中0≤𝑚≤𝑛≤106，𝑃为大质数。根据𝑛𝑚=𝑛!𝑚!𝑛−𝑚!，显然可以用O(𝑚log𝑚)的方法暴力。为了利用预处理加速计算，需要处理𝑛!−1，由逆元的积性，可得𝑛!−1≡𝑘!−1≡𝑓𝑘mod𝑃𝑛𝑘=1𝑛𝑘=1。这样也就能线性预处理阶乘的逆元了。有了这个之后，某些组合计数问题里就能派上用场。例题1给出𝑇组𝑁,𝑀，依次求出gcd(𝑎,𝑏)𝑀𝑏=1𝑁𝑎=1的值。𝑁,𝑀≤106,𝑇≤103根据前面提到的一个结论𝜑(𝑑)𝑑|𝑛=𝑛，我们来对要求的东西进行化简。分析gcd(𝑎,𝑏)𝑀𝑏=1𝑁𝑎=1=𝜑(𝑑)𝑑|gcd(𝑎,𝑏)𝑀𝑏=1𝑁𝑎=1=𝜑(𝑑)𝑑|𝑎and𝑑|𝑏𝑀𝑏=1𝑁𝑎=1=𝜑𝑑11≤𝑏≤𝑀and𝑑|𝑏1≤𝑎≤𝑁and𝑑|𝑎=𝜑𝑑11≤𝑎≤𝑁and𝑑|𝑎×11≤𝑏≤𝑀and𝑑|𝑏=𝜑(𝑑)𝑁𝑑𝑀𝑑分析现在原式被化简成了𝜑(𝑑)𝑁𝑑𝑀𝑑，到这一步的话，如果通过线性筛法预处理欧拉函数，单次询问的时间复杂度为Omin𝑁,𝑀。下面考虑如何继续优化。首先很容易看出𝑁𝑑的取值只有2𝑁种，同理𝑀𝑑的取值只有2𝑀种，并且相同取值对应的𝑑是一个连续的区间，因此𝑁𝑑和𝑀𝑑都相同的区间最多只有2𝑁+2𝑀个，这样𝑑的枚举量就缩小为O𝑁+𝑀了，注意需要预处理𝜑函数的部分和。扩展将原题中的gcd(𝑎,𝑏)𝑀𝑏=1𝑁𝑎=1换成lcm(𝑎,𝑏)𝑀𝑏=1𝑁𝑎=1，数据范围不变。由于lcm𝑎,𝑏=𝑎𝑏/gcd𝑎,𝑏，通过设gcd𝑎,𝑏=𝑑进行化简，也可以得出单次询问O𝑁+𝑀的算法，具体过程比原题要复杂一些，留给大家自己推导。（下面三张隐藏幻灯片为具体的推导过程）分析lcm(𝑎,𝑏)𝑀𝑏=1𝑁𝑎=1=𝑎𝑏𝑑1≤𝑏≤𝑀andgcd(𝑎,𝑏)=𝑑𝑁𝑎=1𝑑=𝑑gcd𝑎,𝑏=1𝑎𝑏𝑀/𝑑𝑏=1𝑁/𝑑𝑎=1令𝑓𝑛,𝑚=gcd𝑎,𝑏=1𝑎𝑏𝑚𝑏=1𝑛𝑎=1𝑓𝑛,𝑚=𝑎𝑏𝜇(𝑑)𝑑|gcd(𝑎,𝑏)𝑚𝑏=1𝑛𝑎=1=14𝜇𝑑𝑑2𝑛𝑑𝑚𝑑𝑛𝑑+1𝑚𝑑+1分析将𝑓𝑛,𝑚代回原式：lcm(𝑎,𝑏)𝑀𝑏=1𝑁𝑎=1=14𝑑𝜇𝑑′𝑑′2𝑁𝑑𝑑′𝑀𝑑𝑑′𝑁𝑑𝑑′+1𝑀𝑑𝑑′+1=14𝑑𝜇𝑑′𝑑′2𝑁𝑑𝑑′𝑀𝑑𝑑′𝑁𝑑𝑑′+1𝑀𝑑𝑑′+1=14𝑁𝑑𝑀𝑑𝑁𝑑+1𝑀𝑑+1𝑑𝑑′𝜇(𝑑′)𝑑′|𝑑令𝑔𝑛=𝑛𝑑𝜇(𝑑)𝑑|𝑛，不难看出𝑔(𝑛)满足积性，可以通过线性筛法预处理。分析其实前面用了一个有趣的结论：若连续且单调增的函数𝑓(𝑥)满足当𝑓(𝑥)为整数时可推出𝑥为整数，则𝑓(𝑥)=𝑓(𝑥)。令𝑓𝑥=𝑥𝑘（𝑘为正整数），可以得到𝑥𝑘=𝑥𝑘，因此推导过程中的𝑁𝑑𝑑′=𝑁𝑑𝑑′。例题2给出𝑇组𝑁,𝑀，依次求出[gcd𝑎,𝑏=1]𝑀𝑏=1𝑁𝑎=1的值。𝑁,𝑀≤106,𝑇≤103这回需要用到的结论是𝜇(𝑑)𝑑|𝑛=[𝑛=1]。分析[gcd𝑎,𝑏=1]𝑀𝑏=1𝑁𝑎=1=𝜇(𝑑)𝑑|gcd(𝑎,𝑏)𝑀𝑏=1𝑁𝑎=1=𝜇(𝑑)11≤𝑏≤𝑀and𝑑|𝑏1≤𝑎≤𝑁and𝑑|𝑎=𝜇𝑑𝑁𝑑𝑀𝑑下面就和前一题一样了。从另外一个角度，我们也能把最终的结果理解为容斥原理。例题3给出𝑇个𝑁，依次计算lcm(𝑎,𝑏)𝑁𝑏=1𝑁𝑎=1𝑁,𝑇≤106由于这次只有一个自变量，会想到设𝑓𝑁=lcm(𝑎,𝑏)𝑁𝑏=1𝑁𝑎=1。很不巧的是，𝑓函数不满足积性。重新令𝑓𝑛=−𝑛+2lcm(𝑛,𝑖)𝑛𝑖=1，容易发现lcm(𝑎,𝑏)𝑁𝑏=1𝑁𝑎=1=𝑓(𝑖)𝑁𝑖=1。算出某些𝑓值可以发现𝑓函数似乎满足积性。分析下面我们来尝试化简𝑓函数。设gcd𝑛,𝑖=𝑑，则𝑓𝑛=−𝑛+2𝑛𝑖𝑑𝑛𝑖=1𝑓𝑛=−𝑛+2𝑛𝑖𝑑𝑖≤𝑛andgcd𝑛,𝑖=𝑑𝑑|𝑛=−𝑛+2𝑛𝑘𝑘≤𝑛𝑑andgcd𝑛𝑑,𝑘=1𝑑|𝑛=−𝑛+2𝑛𝑘𝑘≤𝑑andgcd𝑑,𝑘=1𝑑|𝑛=−𝑛+2𝑛𝑑𝜑𝑑2𝑑|𝑛and𝑑1+1=𝑛𝑑𝜑(𝑑)𝑑|𝑛分析由于𝑓𝑛=𝑛𝑑𝜑(𝑑)𝑑|𝑛，因此𝑓𝑛是积性函数，并且𝑓𝑝𝑘=𝑝𝑘+𝑝𝑘(𝑝−1)𝑝2𝑖−1𝑘𝑖=1=𝑝3𝑘+1+𝑝𝑘𝑝+1因此𝑓𝑝𝑘=𝑝3𝑓𝑝𝑘−1−𝑝𝑘𝑝−1，后面的部分是𝑝𝜑(𝑝𝑘)，因此求解𝑓𝑝𝑘时顺便利用筛法维护欧拉函数就行了。𝑓𝑝𝑘解决后，任意𝑓(𝑛)的值也就能算了。Thankyou