线性筛与莫比乌斯反演
和上篇文章一样，一直没有研究这个东西，结果又考了GG……TAT
下定决心学一学，搞好这个东西。
线性筛
筛质数有很多方法，好像很厉害的有洲阁筛、杜教筛（
然而我都不会QAQ），比较坑的有暴力筛（就是枚举一个数的倍数）。
我只学了比较简单而且实用的线性筛法。
这种筛法是避免一个数被重复筛几遍，所以效率均摊下来可以达到线性。(网上有证明)
先上代码：
const int N = 100000;
bool is_prime[N+100];
int prime[N], cnt = 0;
void find_prime() {
Set(is_prime, true);
is_prime[0] = is_prime[1] = false;
For(i, 2, N) {
if (is_prime[i])
prime[++cnt] = i;
For(j, 1, cnt) {
if (i * prime[j] > N) break;
is_prime[i * prime[j] ] = false;
if (i % prime[j] == 0) break; //here
}
}
}这个代码有一个关键点 就是上面的\(here\) 这个意义就是
对于一个合数\(m\)可以分解为\(m=p_1^{r_1}*...*p_n^{r_n}\)其中
\(p_i\)为质数，那么我们筛\(m\)的时候之前把\(p_1\)筛掉了，所以在
枚举\(i\)的时候。
如果\(i\)为素数没问题，直接向后继续推（因为筛出的
质数都类似\(m=p_1*p_2\)的形式，所以不可能重复）。如果为合数，那么\(i\)可以分解成\(i=p_1^{r_1}*...*p_n^{r_n}\)形式
其中\(p_1-p_n\)是递增的，那么\(p_1\)是最小的那个质数。\(i \bmod p_1 = 0\)的时候，就不用继续枚举了，
所以我们就只能筛出不大于\(p_1\)的质数\(*i\)。
莫比乌斯反演
莫比乌斯反演很多时候都能大大简化运算……
- 定理：\(F(n)\)和\(f(n)\)是定义在非负整数集合上的两个
函数，并且满足条件\(F(n)=\sum \limits \limits _{d|n}{f(d)}\)。那么我们
就能得到结论：
\(f(n)=\sum \limits \limits _{d|n}\mu(d)F(\frac{n}{d})\)
在上面的公式中有一个\(\mu(d)\)函数，它的定义如下：
(1)若\(d=1\),那么\(\mu(d)=1\)
(2)若\(d=p_1p_2...p_k\)，\(p_i\)均为互异质数，
那么\(\mu(d)=(-1)^{k}\)。这个我的理解就是\(d\)的
质因数个数为偶数的话，那么\(\mu(d)=1\)否则为\(-1\)
(3)其他情况下\(\mu(d)=0\)这个就是对上面那条的拓展了，
就是指的\(d\)没有一个平方因子，或者说没有一个质因子的
次数大于\(1\)
线性筛求莫比乌斯函数的代码：
const int N = 100100;
bool is_prime[N+100];
int mu[N+100] = {0, 1}, cnt = 0, prime[N+100];
void init() {
Set(is_prime, true);
is_prime[1] = false;
For (i, 2, N) {
if (is_prime[i]) {
prime[++cnt] = i;
mu[i] = -1; //质数的质因子个数肯定为奇数个就是1
}
For (j, 1, cnt) {
if (i * prime[j] > N) break;
is_prime[i * prime[j] ] = false;
if (i % prime[j]) mu[i * prime[j] ] = -mu[i]; //多了一个质因子直接变为原来结果的相反数
else {
mu[i * prime[j]] = 0; //这个将要被筛的数至少具有两个prime[j]的因子
break;
}
}
}
}有了上面的知识，现在，我们来证明莫比乌斯反演定理。
证明：
\(\sum \limits _{d|n}\mu(d)F(\frac{n}{d})=\sum \limits_{d|n}\mu(d)\sum \limits_{d‘|\frac{n}{d}}f(d‘) =\sum \limits \limits _{d‘|n}f(d‘)\sum \limits_{d|\frac{n}{d‘}}\mu(d)=f(n)\)
Q.E.D
- 然后还要提一下的就是一些常见的定理，证明嘛……
- 一般都是先分解质因数，然后再根据组合数性质去算，比如第一个。
- 要么就是对于一些常见的反演格式进行反演，比如第二个。
- \(\sum \limits _{d|n} \mu(d)=[n=1]\)
- \(\sum \limits _{d|n} \frac{\mu(d)}{d}=\frac{\varphi(n)}{n}\)
一些例题（难题）
题意
求 \(\sum \limits _{i=1}^{n} \sum \limits_{i=1}^{m} lcm(i,j) \ (n,m \le 10^7)\)
题解
一个莫比乌斯反演然后化式子。
\(\sum \limits \limits _{i=1}^{n} \sum \limits_{i=1}^{m} lcm(i,j)\)
\(=\sum \limits \limits _{i=1}^{n} \sum \limits_{i=1}^{m} \frac{i\ j}{gcd(i,j)}\)
\(=\sum \limits \limits _{d=1}^{min(n,m)} \ d \sum \limits_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum \limits_{j=1}^{\lfloor \frac{m}{d} \rfloor} \ ij \ [gcd(i,j)=1]\)
这个就是一个更换枚举相的操作了，是个套路。
你先枚举所有可能的\(gcd\)再计算这种\(gcd\)的贡献。
比如前面的那个\(d\)就是我们枚举的\(gcd\)，后面所有可能的数对，就是在\(\lfloor \frac{n}{d} \rfloor\)和\(\lfloor \frac{m}{d} \rfloor\)中的所有互质的数对的乘积在乘上\(d\)。
这个可以简单理解一下，就是两个数分别除以他们的最大公因数，然后两个数肯定是互质的。
但其对于答案的贡献就多除以了一个\(d\)，所以要乘回来。
\(ans =\sum \limits _{d=1}^{min(n,m)} \ d \sum \limits_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum \limits_{j=1}^{\lfloor \frac{m}{d} \rfloor} \sum \limits_{x|gcd(i,j)}\mu(x) * i * j\)
这个就是运用了前面的公式\(\sum \limits _{d|n} \mu(d)=[n=1]\)来替代了\([gcd(i,j)=1]\)的条件。（这个就是套路了）
然后我们继续推：
\(ans =\sum \limits \limits _{d=1}^{min(n,m)} d \sum \limits_{x=1}^{min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)} \mu(x) \ x^2 \sum \limits_{i=1}^{\lfloor \frac{n}{dx} \rfloor} i \sum \limits_{j=1}^{\lfloor \frac{m}{dx} \rfloor} j\)
这个也是套路，把\(x\)提前了。就是改成了枚举\(x\)看看它的对于答案的贡献是多少。
很容易发现，就是在\([1,\lfloor \frac{n}{dx} \rfloor]\)中的所有数乘上\(x\)
就是原来可行的\(i\)。然后我们就可以根据这个来优化了。
前面那两个\(\sum \limits\)就是\(n \ ln \ n\)（令\(n=max(n,m)\)）的复杂度。（就是\(\sum \limits \limits _{i=1}^{n} \frac{n}{i}\)）。后面的那两个，直接用等差数列求和公式\(O(1)\)算。
但这个仍然过不去...（\(O(1.61*10^8)\)，$ % $的常数还很大）所以就需要来用套路的整除分块了。
就是把后面两个 \(\sum \limits\) 很多一样答案的地方一起处理掉，所以对于那个 \(\mu(x) \ x^2\) 还要记一个前缀和。
总复杂度\(O(\sum \limits _{i=1}^{n} \sqrt{\frac{n}{i}})=O(pass)\)这个我也不会算。。大佬说似乎是\(O(n^{\frac{2}{3}})\)。