线性筛

引入

线性筛，通常用于筛积性函数

线性筛素数

inline void init(int n) {
	memset(IsPrime, true, sizeof(IsPrime));
	tot = 0;
	IsPrime[1] = false;
	
	for (int i = 2; i <= n; ++i) {
		if (IsPrime[i])
			prime[++tot] = i;
		
		for (int j = 1; j <= tot && i * prime[j] <= n; ++j) {
			IsPrime[i * prime[j]] = false;
			
			if (!(i % prime[j]))
				break;
			
			// i 被 prime[j] 筛过了，故 i 乘上更大的数一定被prime[j]筛过
		}
	}
}

线性筛欧拉函数

注意到在线性筛中每个合数都是被最小的质因子筛掉，分类讨论 \(i \bmod prime_j\) 的情况

• \(i \bmod prime_j = 0\)

  此时 \(i\) 包含了 \(i \times prime_j\) 的所有质因子，则

  \[\begin{aligned} \varphi(i \times prime_j) &= i \times prime_j \times \prod \dfrac{p_k - 1}{p_k} \\ &= p_1 \times i \times \prod \dfrac{p_k - 1}{p_k} \\ &= p_1 \times \varphi(i) \end{aligned} \]

• \(i \bmod prime_j \not = 0\)

  此时 \(i, prime_j\) 互质，故 \(\varphi(i \times prime_j) = \varphi(i) \times \varphi(prime_j)\)

inline void init(int n) {
	memset(IsPrime, true, sizeof(IsPrime));
	tot = 0;
	IsPrime[1] = false, phi[1] = 1;
	
	for (int i = 2; i <= n; ++i) {
		if (IsPrime[i])
			prime[++tot] = i, phi[i] = i - 1;
		
		for (int j = 1; j <= tot && i * prime[j] <= n; ++j) {
			IsPrime[i * prime[j]] = false;
			
			if (i % prime[j])
				phi[i * prime[j]] = phi[prime[j]] * phi[i];
			else {
				phi[i * prime[j]] = prime[j] * phi[i];
				break;
			}
		}
	}
}

线性筛莫比乌斯函数

inline void init(int n) {
	memset(IsPrime, true, sizeof(IsPrime));
	tot = 0;
	IsPrime[1] = false, mu[1] = 1;
	
	for (int i = 2; i <= n; ++i) {
		if (IsPrime[i])
			prime[++tot] = i, mu[i] = -1;
		
		for (int j = 1; j <= tot && i * prime[j] <= n; ++j) {
			IsPrime[i * prime[j]] = false;
			
			if (i % prime[j])
				mu[i * prime[j]] = -mu[i];
			else {
				mu[i * prime[j]] = 0;
				break;
			}
		}
	}
}

线性筛约数个数

\(d_i\) 表示 \(i\) 的约数个数， \(c_i\) 表示 \(i\) 的最小质因子出现次数

inline void init(int n) {
	memset(IsPrime, true, sizeof(IsPrime));
	tot = 0;
	IsPrime[1] = false, d[1] = 1;
	
	for (int i = 2; i <= n; ++i) {
		if (IsPrime[i])
			prime[++tot] = i, d[i] = 2, c[i] = 1;
		
		for (int j = 1; j <= tot && i * prime[j] <= n; ++j) {
			IsPrime[i * prime[j]] = false;
			
			if (i % prime[j]) {
				c[i * prime[j]] = 1;
				d[i * prime[j]] = d[i] * 2;
			}
			else {
				c[i * prime[j]] = c[i] + 1;
				d[i * prime[j]] = d[i] / c[i * prime[j]] * (c[i * prime[j]] + 1);
				break;
			}
		}
	}
}

线性筛约数和

\(f_i\) 表示 \(i\) 的约数和， \(g_i\) 表示 \(i\) 的最小质因子的 \(p^0 + p^1 + \cdots + p^k\)

inline void init(int n) {
	memset(IsPrime, true, sizeof(IsPrime));
	tot = 0;
	g[1] = f[1] = 1;
	
	for (int i = 2; i <= n; ++i) {
		if (IsPrime[i])
			prime[++tot] = i, g[i] = i + 1, f[i] = i + 1;
		
		for (int j = 1; j <= tot && i * prime[j] <= n; ++j) {
			IsPrime[i * prime[j]] = false;
			
			if (i % prime[j]) {
				f[i * prime[j]] = f[i] * f[prime[j]];
				g[i * prime[j]] = prime[j] + 1;
			}
			else {
				g[i * prime[j]] = g[i] * prime[j] + 1;
				f[i * prime[j]] = f[i] / g[i] * g[i * prime[j]];
				break;
			}
		}
	}
}