线性筛
约 299 个字 130 行代码 预计阅读时间 3 分钟
线性筛(又名欧拉筛)¶
筛出1-N所有质数
原理¶
线性筛在埃氏筛上更进一步,让每个合数只被它的最小质因子筛选一次,减少了重复
时间复杂度¶
O(n)
const int N=1e7+3;
bitset<N> v;
int p[N>>2];//存放素数
void Euler_seive()
{
int cnt=0;
v[1]=1;//1既不是质数也不是合数
for(int i=2;i<N;++i)
{
if(!v[i])
p[cnt++]=i;
for(int j=0;j<cnt && i*p[j]<N;++j)
{
v[i*p[j]]=1;
if(i%p[j]==0)//减少重复筛
break;
}
}
}
可以用线性筛求一些积性函数
数论函数(又称算术函数)¶
在数论上,指定义域为正整数、陪域为复数的函数
陪域¶
在映射f:X→Y 中,X称为定义域,Y称为陪域。
对于某个映射来说,它的值域一定为陪域的子集
积性函数¶
数论函数中
若p,q互质,满足 f[p*q]=f[p]*f[q],则f为积性函数
若任意p,q,满足f[p*q]=f[p]*f[q],则f为完全积性函数
如1函数,即f[x]=1
积性函数性质可知,f[1]=1
常见积性函数¶
欧拉函数φ¶
表示1-n,和n互质的数的个数
const int N=1e7+3;
int v[N],p[N>>2],phi[N];
void getphi()
{
int cnt=0;
phi[1]=1;
for(int i=2;i<N;++i)
{
if(!v[i])
{
p[cnt++]=i;
phi[i]=i-1;
}
for(int j=0;j < cnt && p[j]*i < N;++j)
{
v[i*p[j]]=1;
if(i%p[j]==0)
{
phi[i*p[j]]=phi[i]*p[j];
break;
}
phi[i*p[j]]=phi[i]*phi[p[j]];
}
}
}
莫比乌斯函数μ¶
莫比乌斯反演会用到
有平方因子,函数为0
否则,函数=(-1)^k,k为质因子个数
const int N=1e7+3;
int v[N],p[N>>2],mu[N];
void getmu()
{
int cnt=0;
mu[1]=1;
for(int i=2;i<N;++i)
{
if(!v[i])
{
p[cnt++]=i;
mu[i]=-1;
}
for(int j=0;j < cnt && i*p[j] < N;++j)
{
v[i*p[j]]=1;
if(i%p[j])
mu[i*p[j]]=-mu[i];
else
{
//mu[i*p[j]]=0;
//全局变量初始为0,所以这句可省去
break;
}
}
}
}
约数相关有两种,分别是求约数个数,求约数和
约数个数¶
//dn:divisor number,mpdn:minimum prime divisor number
const int N=1e7+3;
int v[N],p[N>>2],dn[N],mpdn[N];
void getDivisorNumber()
{
int cnt=0;
for(int i=2;i<N;++i)
{
if(!v[i])
{
p[cnt++]=i;
dn[i]=2;
mpdn[i]=1;
}
for(int j=0;j < cnt && i*p[j] < N;++j)
{
v[i*p[j]]=1;
if(i%p[j]==0)
{
mpdn[i*p[j]] = mpdn[i]+1;
dn[i*p[j]]=dn[i]/(mpdn[i]+1)*(mpdn[i]+2);
break;
}
dn[i*p[j]]=dn[i]*dn[p[j]];
mpdn[i*p[j]]=1;
//p[j]是i*p[j]的最小素因子
}
}
}
约数和¶
//sd:sum of divisor,smpd:sum of minimum prime divisor polynomial
//sd约数和,smpd最小质因子的那个多项式(也可以理解为由最小质因子组成的数的约数和吧)
const int N=1e7+3;
int v[N],p[N>>2],sd[N],smpd[N];
void getSumOfDivisors()
{
int cnt=0;
sd[1]=1;
for(int i=2;i<N;++i)
{
if(!v[i])
{
p[cnt++]=i;
sd[i]=i+1;
smpd[i]=i+1;
}
for(int j=0;j<cnt && i*p[j]<N;++j)
{
v[i*p[j]]=1;
if(i%p[j]==0)
{
smpd[i*p[j]]=smpd[i]*p[j]+1;
sd[i*p[j]]=sd[i]/smpd[i]*smpd[i*p[j]];
break;
}
sd[i*p[j]]=sd[i]*sd[p[j]];
smpd[i*p[j]]=p[j]+1;
}
}
}