JZTXT

线性筛

发布时间 2024-01-07 17:19:42作者: Alric
ll n,q,fac[N],mu[N];
vector<ll> prime;
mu[1]=1;
for(ll i=2;i<=n;i++){
	if(fac[i]==0)fac[i]=i,prime.push_back(i),mu[i]=-1;
	for(ll j=0;j<prime.size();j++){
		if(prime[j]>fac[i]||prime[j]>n/i)break;
		fac[i*prime[j]]=prime[j];
		if(i%prime[j])mu[i*prime[j]]=-mu[i];
	}
}