\(OK\)，那这就是我的第一篇博客了\(QwQ\)。
众所周知这个 \(lyy\) 是个 \(big\ \ colorful\ \ pen\) ，他的数学严重限制了他的信竞，所以适当地做做笔记或总结对这个菜得没救了的人也是有点帮助的。
万恶之源，比埃氏筛更优的线性筛，线性体现在每个数会被它最小的质因子筛掉，最小的质因子显然只有一个，每个数只会被访问一次，严格的线性复杂度。
一个数被访问是由枚举“除去它最小的质因子后的值 \(i\) ”，再乘上“最小质因子 \(prime[j]\)（以下简写为\(p[j]\)）”实现的。例如 \(8\) 是在 \(i=4,p[j]=2\) 时被访问的，\(12\) 是在 \(i=6,p[j]=2\) 时被访问的，\(9\) 是 \(i=3,p[j]=3\) （可以看到需要先把 \(i\) 加入质数中再枚举质数）。若当前的 \(i\) 没有被访问，说明 \(i\) 最小的质因子是它本身，显然 \(i\) 就是个质数。
为了保证当前质因子是乘积的最小质因子，当 \(i\%p[j]==0\) 时停止对 \(j\) 的枚举，因为此时 \(i\) 中保证有质因子 \(p[j]\)，当 \(p[j]\) 继续增大时，\(i\) 与 \(p[j]\) 乘积的最小质因子不会再是 \(p[j]\)，而是i中的最小质因子。
for(int i=2; i<=n; i++) {
if(!vis[i]) p[++cnt] = i;
for(int j=1; j<=cnt && i*p[j]<=n; j++) {
vis[ i*p[j] ] = 1;
if(i%p[j]==0) break; //与埃氏筛唯一的区别
}
}
有了线性筛，遇到1e7的毒瘤题也不用慌了。
积性函数是指当 \(a\) 与 \(b\) 互质时满足 \(f(ab)=f(a)*f(b)\) 的函数。常见的像欧拉函数 \(\phi\) ，约数个数 \(d\)， 约数和 \(\sigma\)，莫比乌斯函数 \(\mu\)。所有的积性函数都能线筛（大概）。
我们在线性筛时，每个数是由 \(i\) 与 \(p[j]\) 乘起来得到的。
若 \(i\%p[j]!=0\)，因为 \(p[j]\) 是质数所以 \(i\) 与 \(p[j]\) 互质，\(f( i*p[j] )=f(i)*f(p[j])\)。
若 \(i\%p[j]=0\)，我们一般需要考虑这个数中最小的质因子 \(p[j]\) 的出现次数对它函数值的影响，一般需要另设一个函数 \(g\) 来记录最小质因子的出现次数，当 \(i\%p[j]=0\) 时，\(g[i*p[j]]=g[i]+1\)，而 \(f\) 值就要具体情况具体分析了。
欧拉函数 \(\phi\)，表示比 \(x\) 小的与 \(x\) 互质的数的个数，求单个的话是 \(sqrt\) 复杂度的。
若\(x=p_1^{k1}*p_2^{k2}*p_3^{k3}...p_n^{kn}\)，则\(\phi(x)=x\prod\limits_{i=1}^n\dfrac {p_i-1} {p_i}\)。这个很好证，就是考虑每个质因子对 \(\phi\) 值的贡献。
\(\phi\) 是积性函数也就显然了，因为互质的两个数没有相同的 \(p\)，两个数的质因子贡献互不影响。
所以当 \(i\%p[j]!=0\) 时，\(\phi(i*p[j])=\phi(i)*\phi(j)=\phi(i)*(p[j]-1)\)；
当 \(i\%p[j]=0\) 时，由于 \(p[j]\) 已经在 \(i\) 中出现，所以乘上 \(p[j]\) 不会对 \(\phi\) 造成影响，\(\phi(i*p[j])=\phi(i)*p[j]\)。
for(int i=2; i<=n; i++) {
if(!vis[i]) {
p[++cnt] = i;
phi[i] = i-1;
}
for(int j=1; j<=cnt && i*p[j]<=n; j++) {
vis[ i*p[j] ] = 1;
if(i%p[j]==0) {
phi[ i*p[j] ] = phi[i] * p[j];
break;
}
phi[ i*p[j] ] = phi[i] * (p[j]-1);
}
}
一个显然的结论：若\(x=p_1^{k1}*p_2^{k2}*p_3^{k3}...p_n^{kn}\)，则\(d(x)=\prod\limits_{i=1}^n(k_i+1)\)。若x与y互质，那么x与y没有相同的质因子，显然\(d(xy)=d(x)*d(y)\)，所以 \(d\) 是个积性函数。
考虑同样的线筛方式，当 \(i\%p[j]!=0\) 时，\(d(i*p[j])=d(i)*d(p[j])=d(i)*2\)；
当 \(i\%p[j]=0\) 时，相当于 \(p[j]\) 的指数从 \(k_j\) 变成了 \(k_j+1\)，辣么它的d就从一大坨乘上 \(k_j+1\) 变成一大坨乘上 \(k_j+2\) ，所以有必要开一个 \(g\) 记录最小质因子出现次数，\(g[ i*p[j] ]=g[i]+1,d[i*p[j]]=d[i]/(g[i]+1)*(g[i]+2)\)。记得当 \(i\) 是质数时，\(d[i]=2,g[i]=1\)。
d[1] = 1;
for(int i=2; i<=n; i++) {
if(!vis[i]) {
p[++cnt] = i;
d[i] = 2; g[i] = 1;
}
for(int j=1; j<=cnt && i*p[j]<=n; j++) {
vis[ i*p[j] ] = 1;
if(i%p[j]==0) {
d[ i*p[j] ] = d[i] / (g[i]+1) * (g[i]+2);
g[ i*p[j] ] = g[i] + 1;
break;
}
d[ i*p[j] ] = d[i] * 2;
g[ i*p[j] ] = 1;
}
}
前方施工中。。。
原文：https://www.cnblogs.com/clever-sheep/p/12741425.html