【模板】各类线性筛法

线性筛法是极其实用而高效的方法，一般是对于数论上的完全积性函数和积性函数才使用这种方法。

积性函数的定义：

• 对于互质的正整数(p_1p_2)，我们若有在正整数域上定义的函数，(f(ab)=f(a)f(b))，则称(f(x))为积性函数。若(p_1p_2)扩展到整数域内，则称为完全积性函数。

我们的线性筛法就是基于这样的数学原理，其中，线性筛素数是基础

线性筛素数

(以下代码默认):

#define RP(t,a,b) for(int t=(a),edd=(b);t<=edd;t++)

思想:

1. 当我们更新到(i)时，我们判断它是否是一个合数(是否被标记过)，否则是个质数，加入素数表中。
2. 将(i×prime(j),)注意(i)不能(|prime(j)),若发生整除则break，这保证了线性的复杂度

const int maxn=100005;
bool pr[maxn];
vector < int > prime;
inline void gen_prime(){
	RP(t,1,maxn-5)
		pr[t]=1;
	pr[0]=pr[1]=false;
	RP(t,2,maxn-5){
		if(pr[t])
			prime.push_back(t);
		RP(i,0,prime.size()-1){
			if(t*prime[i]>maxn)
				break;
			pr[t*prime[i]]=false;
			if(!(t%prime[i]))
				break;
		}
	}
	return;
}

线性筛(phi)函数,欧拉函数：

关于欧拉函数:

1. 对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）
2. 对于质数(p),显然有(phi(p)=p-1)
3. 对于奇数(p)，易得(phi(p)=phi(2p))
4. 和费马小定理定理的联系

   • (a^{phi(m)} equiv1pmod{m})

   • 当(m)是质数时,
   • (a^{m} equiv a pmod{m})

思想:（对于质数(p)）

1. 对于(p_1p_2)互质， (phi(p_1 imes p_2)=phi(p_1) phi(p_2))
2. 若(imod p= 0), 那么(phi(i * p)=p imes phi(i))证明略
3. 若(i mod p ≠0), 那么(phi(i imes p)=phi(i) imes(p-1))
4. 质数和欧拉函数一起筛。

const int maxn=100005;
vector < int > prime;
int phi[maxn];
bool usd[maxn];
inline void gen_phi(void){
	int cnt=0;
	phi[1]=1;
	RP(t,2,maxn-5){
		if(!phi[t])
			phi[t]=t-1,prime.push_back(t);
		RP(i,0,prime.size()-1){
			if(prime[i]*t>maxn)
				break;
			if(!t%prime[i]){
				phi[t*prime[i]]=phi[t]*prime[i];
				break;
			}
			else
				phi[t*prime[i]]=phi[t]*phi[prime[i]];
		}
	}
}

线性筛莫比乌斯函数,(mu(x))

思想:

1. 莫比乌斯函数只有(0,1,-1)三种值。
2. 对于(x=p_1p_2p_3p_4p_5p_6...p_n)，(p_i)为互不相同的质数，(mu(x)=(-1)^n)
3. 其他情况都为0

const int maxn=100005;
vector < int > prime;
int mu[maxn];
bool usd[maxn];
inline void gen_mu(void){
	mu[1]=1;
	RP(t,2,maxn){
		if(!usd[t])
			prime.push_back(t),mu[t]=-1;
		RP(i,0,prime.size()-1){
                        if(prime[i]*t>maxn)
                            break;
			usd[prime[i]*t]=1;
			if(!(t%prime[i]))
				break;
			else
				mu[t*prime[i]]=-mu[t];
		}
	}
}