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];
}
}
线性筛
发布时间 2024-01-07 17:19:42作者: Alric