博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
线性筛法及积性函数总结(欧拉函数、莫比乌斯函数、约数和函数、约数个数函数)...
阅读量:5840 次
发布时间:2019-06-18

本文共 4330 字,大约阅读时间需要 14 分钟。

  线性筛法在数论中起着至关重要的作用,对于一部分求解有关积性函数的问题可以大大降低时间复杂度。线性筛法中,除了线性筛质数,所要筛的函数必须是积性函数,而线性筛这些函数的基础也是线性筛质数。先来解释一下什么是积性函数?积性函数就是指对于一个函数f,f(1)=1且对于任意两个互质的数x,y满足f(x)*f(y)=f(x*y)。而如果任意两个数x,y都满足以上等式,那么这个函数就是完全积性函数。

常见且实用的积性函数有:

1、l(x)=1,也叫单位函数,卷积单位元

2、id(x)=x

3、Φ(x),欧拉函数,1~x中与x互质的数的个数

4、μ(x),莫比乌斯函数,当x=1时,函数值为1;当x为k个质数的一次幂乘积时,函数值为(-1)k;其他情况为0

下面进入正题:

为了方便描述,设f[]为对应积性函数,p[]为存质数的数组,p[j]是i的最小质因子,prime[j]与p[j]同义

一、欧拉函数

1、性质

  • 若p为质数,则Φ(p)=p-1
  • 若x与y互质,则Φ(x*y)=Φ(x)*Φ(y)
  • 若n为奇数,则Φ(2n)=Φ(n),(其实就是上一个性质的特殊情况)
  • 若n为质数p的k次幂,则Φ(n)=(p-1)*pk-1,(除p的倍数外都与n互质)
  • Σd|nΦ(d)=n

2、线性筛

当i为质数时,f[i]=i-1

当i%p[j]!=0时,i与p[j]互质,f[i*p[j]]=f[i]*(p[j]-1)

当i%p[j]==0时,设ak为i的一个质因子,Φ(i)=i*Π((ak-1)/ak),因此f[i*p[j]]=p[j]*f[i]

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long longusing namespace std;bool vis[10000010];int n;int f[10000010];int prime[1000000];int cnt;void find(){ f[1]=1; for(int i=2;i<=n;i++) { if(!vis[i]) { prime[++cnt]=i; f[i]=i-1; } for(int j=1;j<=cnt&&i*prime[j]<=n;j++) { vis[i*prime[j]]=1; if(i%prime[j]==0) { f[i*prime[j]]=prime[j]*f[i]; break; } else { f[i*prime[j]]=(prime[j]-1)*f[i]; } } }}int main(){ scanf("%d",&n); find();}

二、莫比乌斯函数

1、性质

  • Σd|nμ(d)=ε(n),当n=1时,ε(n)=1;当n≠1时,ε(n)=0,(莫比乌斯反演用到的重要性质)

2、线性筛

当i为质数时,f[i]=-1

当i%p[j]!=0时,说明i中没有p[j],那么f[i*p[j]]=-f[i]

当i%p[j]==0时,f[i*p[j]]=0

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long using namespace std;bool vis[10000010];int n;int f[10000010];int prime[1000000];int cnt;void find(){ f[1]=1 for(int i=2;i<=n;i++) { if(!vis[i]) { prime[++cnt]=i; f[i]=-1; } for(int j=1;j<=cnt&&i*prime[j]<=n;j++) { vis[i*prime[j]]=1; if(i%prime[j]==0) { f[i*prime[j]]=0; break; } else { f[i*prime[j]]=-f[i]; } } }}int main(){ scanf("%d",&n); find();}

三、约数个数函数

1、性质

对于任意一个大于1的正整数n都能质因数分解为n=p1a1*p2a2*……*pkak,f(n)=(1+a1)*(1+a2)*……*(1+ak)

2、线性筛

因为每个数由它最小的质因子筛出,因此要开一个辅助数组d[i]表示i最小质因子的次幂

当i为质数时,f[i]=2,d[i]=1

当i%p[j]!=0时,由于是积性函数,f[i*prime[j]]=f[i]*f[prime[j]]=2*f[i],d[i]=1

当i%p[j]==0时,根据性质可知f[i*prime[j]]=f[i]/(d[i]+1)*(d[i]+2),d[i*prime[j]]=d[i]+1

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long using namespace std;bool vis[10000000];int n;int f[10000000];int prime[10000000];int d[10000000];int cnt;void find(){ f[1]=1; for(int i=2;i<=n;i++) { if(!vis[i]) { prime[++cnt]=i; f[i]=2; d[i]=1; } for(int j=1;j<=cnt&&i*prime[j]<=n;j++) { vis[i*prime[j]]=1; if(i%prime[j]==0) { f[i*prime[j]]=f[i]/(d[i]+1)*(d[i]+2); d[i*prime[j]]=d[i]+1; break; } else { f[i*prime[j]]=2*f[i]; d[i*prime[j]]=1; } } }}int main(){ scanf("%d",&n); find();}

 四、约数和函数

1、性质

对于任意大于1的正整数质因数分解,n=p1a1*p2a2*……*pkak

f(n)=(1+p11+p12+……+p1a1)*(1+p21+p22+……+p2a2)*……*(1+pk1+pk2+……+pkak)

2、线性筛

设d[i]表示i最小质因子的各次幂之和

当i为质数时,f[i]=i+1,d[i]=i+1

当i%p[j]!=0时,f[i*p[j]]=f[i]*f[p[j]],d[i*p[j]]=1+p[j],积性函数性质

当i%p[j]==0时,d[i*p[j]]=d[i]*p[j]+1,f[i*p[j]]=f[i]/d[i]*d[i*p[j]]

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long using namespace std;bool vis[10000000];int n;ll f[10000000];int prime[10000000];ll d[10000000];int cnt;void find(){ f[1]=1; for(int i=2;i<=n;i++) { if(!vis[i]) { prime[++cnt]=i; f[i]=i+1; d[i]=i+1; } for(int j=1;j<=cnt&&i*prime[j]<=n;j++) { vis[i*prime[j]]=1; if(i%prime[j]==0) { d[i*prime[j]]=d[i]*prime[j]+1; f[i*prime[j]]=f[i]/d[i]*d[i*prime[j]]; break; } else { f[i*prime[j]]=f[i]*f[prime[j]]; d[i*prime[j]]=1+prime[j]; } } }}int main(){ scanf("%d",&n); find();}

 总结:

  线性筛积性函数的方法一般都相同,都是利用积性函数互质可相乘的性质来筛。

  具体说一下方法:

  • 首先需要一个数组g[i]存i最小质因子的最高次幂的乘方,所要筛的积性函数还是用f[i]来表示,p[j]表示i的最小质因子。
  • 当i为质数时,直接求就好了。
  • 当i%p[j]!=0时,由积性函数性质直接相乘->f[i*prime[j]]=f[i]*f[prime[j]],d[i*prime[j]]=prime[j]
  • 当i%p[j]==0时,这时设t=i/d[i],t就与p[j]互质了,i*prime[j]=t*prime[j]*d[i],f[i*prime[j]]=f[t]*f[prime[j]*d[i]],d[i*prime[j]]=d[i]*prime[j]
  • 但当i=pk形式的数时,这么做是不行的,我们就只能暴力求了。

转载于:https://www.cnblogs.com/Khada-Jhin/p/9513533.html

你可能感兴趣的文章
MySQL Replication主主复制—(实例)
查看>>
javascript的使用(2)函数的使用
查看>>
zookeeper下载安装
查看>>
关于java new 创建对象的问题
查看>>
Android性能优化
查看>>
iOS开发中常见错误
查看>>
log4j.properties配置说明
查看>>
【“零起点”--百度地图手机SDK】如何创建一张地图
查看>>
我对搜索引擎优化的一些心得,小部分是课本上的
查看>>
虚拟机ping不通本机
查看>>
go的遍历数组操作
查看>>
建设容易选型难 数据中心高密度交换机
查看>>
华为交换机5700 ACL配置
查看>>
决定边缘计算未来形态的五大需求
查看>>
Nginx+Tomcat 安装配置
查看>>
Esxi 下虚拟主机安装Vmware Tools
查看>>
Linux下的postfix安装详解
查看>>
新手学习oracle之迁移数据表空间
查看>>
JS学习随笔记录1
查看>>
Linux的inode的理解
查看>>