筛法 - Sieve
Changelog Update 2021.10.03 增加PN筛 包含有: 线性筛,杜教筛,Min25筛,PN筛,州阁筛 本篇主要用于入门数论中的一些简单的筛法 虽然不是特别全面,但是后面会一步步完善的。 注意:不会对用到的数论函数解释,默认读者对数论有基本认知。 线性筛 从名字也可以看出,这种筛法为线性复杂度。 我们主要用它来得到某个积性函数函数值的表,(在线性的时间复杂度内得到)。 线性筛的基本思路,对于某个合数$n$,若它的最小质因子为$p$: 如果$(p,\frac{n}{p})\not = 1$,考虑函数本身,主要看质因子指数对函数值的影响。 如果$(p, \frac{n}{p})=1$,由积性函数的性质$f(n)=f(\frac{n}{p})f(p)$。 质数筛(顺便记录最小素因子) 按照合数的定义就知道了。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int lpf[LIM]; vector<int> sieve() { vector<int> pr; for (int i = 2; i < LIM; i++) { if (lpf[i] == 0) { lpf[i] = i, pr.push_back(i); } for (const int &p : pr) { ll j = p * 1LL * i; if (j >= LIM) break; lpf[j] = p; if (i % p == 0) break; } } return pr; } 欧拉函数筛 设$(n,m)=d$,则有...