积性函数线性筛

前言

有关积性函数的相关性质，请参考莫比乌斯反演。

与线性筛关系最大的便是以下性质：

$gcd(a,b)=1$时，满足$f(ab)=f(a)f(b)$

实现方法

首先明确一点，所有的线性筛出积性函数的方法都是通过线性筛素数实现的。

如何筛素数？

朴素筛法（复杂度$O(n^2)$~$O(n\sqrt {n})$）

枚举每一个数和它的因子，如果只有1与它本身是它的因子，那么它就是质数。

因为所有$>\sqrt{n}$的因子都可以被小于$\sqrt{n}$的因子表示，所以可以只枚举到$\sqrt{n}$，但是复杂度还是不够优秀。

埃氏筛（复杂度$O(nloglogn)$）

思想就是从枚举因子转化为枚举倍数。

很明显质数的倍数都不是质数，所以对于每个质数，枚举其倍数，并将其标记成非质数。

很明显这样做的话会使得一些数被筛去好几次，比如6会被2和3筛去，造成了时间上的浪费。

虽然这种筛法在实际应用上有更好的代替，但是其将枚举因子转化为枚举倍数的思想却能够优化解决很多问题。

欧拉筛（复杂度$O(n)$）

为了解决埃氏筛反复筛去一个数多次的问题，我们规定，每一个数只能被其最小的质因子删去。

通过代码进行进一步讲解

#define fr(i, j, k) for(register int i = j; i <= k; ++i)
const int maxn = 40010;
int prime[maxn], tot;
char vis[maxn];
void innt(){
	vis[1] = 1;
	fr(i, 2, maxn - 1){
		if(!vis[i])prime[++tot] = i;
		for(int j = 1; j <= tot && i * prime[j] <= maxn; ++j){
			vis[i * prime[j]] = 1;
			if(i % prime[j] == 0) break;//关键点！！！！！！
		}
	}
}

代码中有一句：

if(i % prime[j] == 0)break;

正是这句话保证了每个数只会被其最小的质因子删去。

线性筛欧拉函数

欧拉函数定义

欧拉函数是指小于x的整数中与x互质的数的个数，用$\varphi$表示，特殊的：$\varphi(1)=1$。

欧拉函数性质

1.对于质数$p$, $\varphi(p)=p-1$

根据定义显然

2.对于质数$p$,

若$p$是$x$的约数，则 $\varphi(xp)=\varphi(x)p$ 。

若p不是x的约数，则 $\varphi(xp)=\varphi(x)\varphi(p)=\varphi(x)*(p-1)$ 。

证明：

1.若$x\%p==0$则$ip$的最小素因子的个数多了1，其余无变化

2.若$x\%p!=0$，因为$\varphi$s是积性函数，所以当$x$与$p$互质时$\varphi(xp)=\varphi(x)*\varphi(p)$。

实现

#define fr(i, j, k) for(register int i = j; i <= k; ++i)
const int maxn = 40010;
int prime[maxn], phi[maxn], tot;
char vis[maxn];
void innt(){
	vis[1] = 1, phi[1] = 1;
	fr(i, 2, maxn){
		if(!vis[i]){prime[++tot] = i;phi[i] = i - 1;}
		for(int j = 1; j <= tot && i * prime[j] <= maxn; ++j){
			vis[i * prime[j]] = 1;
			if(i % prime[j]){
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			phi[i*prime[j]] = phi[i] * (prime[j] - 1);
		}
	}
}

线性筛莫比乌斯函数

莫比乌斯函数定义及性质

请参考莫比乌斯反演。

实现

#define fr(i, j, k) for(register int i = j; i <= k; ++i)
const int maxn = 40010;
int prime[maxn], mu[maxn], tot;
char vis[maxn];
void innt(){
	mu[1] = 1;
	vis[1] = 1;
	fr(i, 2, maxn){
		if(!vis[i])prime[++cnt] = i, mu[i] = -1;
		for(int j = 1, w; j <= cnt && (w = (i * prime[j])) <= maxn; ++j){
			vis[w] = 1;
			if(!(i % prime[j])){mu[w] = 0;break;}
			else mu[w]=-mu[i];
		}
	}
}