Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

欧拉线性筛 和 欧拉函数的求值

Jack_Pei 2019-02-13 23:30:00 阅读数:151 评论数:0 点赞数:0 收藏数:0

PS:求逆元的部分在文章最后。。。最好也看看前边的知识吧qwq


用筛法求素数的基本思想是:把从1开始的、某一范围内的正整数从小到大顺序排列, 1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。依次类推,直到筛子为空时结束。(来自 百度百科)


 一般的筛法(埃拉托斯特尼筛法)的效率是O(nlglgn),但出题人卡你可就凉了。。

(就不介绍了(逃))

下面我们来说O(n)的欧拉线性筛

埃筛之所以慢,是因为有些合数被重复筛除(如:6会被2和3重复筛)

但是欧拉筛保证

每一个数p,只会被其最小的素因子mp[p]筛一次

#define R register int
const
int M=1000010; int mp[M],//mp[i] 为i的最小素因子 prime[M],//prime[i] 代表2-n中的第i个质数 cnt;//素数计数 inline void Prime(int n)//筛的范围 { for(R i=2;i<=n;i++) { if(!mp[i]) prime[++cnt]=mp[i]=i; for(R j=1,k=i*prime[j];j<=cnt&&prime[j]<mp[i]&&(k=i*prime[j])<=m;i++) mp[k]=prime[j]; } }

也有一些别的写法,如

inline void Prime(int x)
{
for(int i=2;i<=x;i++)
{
if(!mp[i]) prime[++cnt]=i,mp[i]=i;
for(int j=1;j<=cnt&&i*prime[j]<=x;j++)
{
mp[i*prime[j]]=prime[j];
if(i%prime[j]==0) break;
//if(prime[j]>=mp[i]) break; 
 }
}
}

 

if(i%prime[j]==0) break; 这个很重要qwq

若 i%prime[j]==0,则 i=k*prime[j](k为正整数).

如果不 break,下一个循环中的 mp(i*prime[j+1])=prime[j+1],

就是 mp(k*prime[j]*prime[j+1])=prime[j+1],

但 显然k*prime[j]*prime[j+1]的最小质因子为 prime[j] 而非 prime[j+1](prime[]数组中的素数是递增的)

所以应 break

if(prime[j]>=mp[i]) break;也可用这句话,一个意思,就是不能让 i乘上的质因子 大于 i的最小质因子


 

欧拉函数。。。

在数论,对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4,因为1,3,5,7均和8互质。

所以求某个φ(p)可以有很朴素(朴素的不行)的求法:

//就是枚举每个素因子
inline int phi(int n)
{
R ans=1;
for(R i=2;i*i<=n;++i) if(n%i==0)
{
n/=i;
ans*=i-1;
while(n%i==0) n/=i,ans*=i;
}
if(n>1) ans*=n-1;
return ans;
}

但如果求p∈[1,n],每个φ(p),那上面的算法就太菜了。

数论上的积性函数f(x)满足a与b互素时(a,b∈N+),f(a·b)=f(a)·f(b),f(1)=1;

而φ(p)就是一个积性函数。

此时可以利用刚学的欧拉筛

正确性:

1.φ(p)是一个积性函数,当a与b互素时,满足φ(a·b)=φ(a)·φ(b)。

2.当正整数p是素数时,φ(p)=p-1 (定义)

3.每个合数只会被筛到一次(前面说明过)。

4.当p是素数时,φ(pk)=(p-1)·φ(pk-1),因为有(p-1)个数与p互素

#define R register int
const int N=10000010;
int n,cnt,prime[N],p[N];
bool vis[N];
inline void Euler(int n)
{
vis[1]=true;
for(R i=2;i<=n;i++)
{
if(!vis[i]) prime[++cnt]=i,p[i]=i-1;
for(R j=1;j<=cnt&&i*prime[j]<=n;j++)
{
vis[i*prime[j]]=true;
if(i%prime[j]==0)
{
p[i*prime[j]]=p[i]*prime[j];
break;
}
p[i*prime[j]]=(prime[j]-1)*p[i];
}
}
}//p[i]即为φ(i)

所以隆重推出......::::::

欧拉定理:

若p,a为正整数,且p,a互质,则:a^φ(p) ≡1 (mod p) (是不是有些眼熟)

其实欧拉定理相当于费马小定理的扩展

所以我们可用其求乘法逆元:

a*a^(φ(p)-1) ≡1 (mod p) 

a^(φ(p)-1)即为a mod p 意义下的逆元

#include<iostream>
#include<cstdio>
#include<cctype>
#define R register int
#define ll long long
using namespace std;
static ll a,p;
inline ll q_pow(ll x,ll ind,ll mod)
{
x%=mod;
register ll a=1;
for(;ind;ind>>=1,(x*=x)%=mod) if(ind&1) (a*=x)%=mod;
return a;
}
inline int phi(int n)
{
R ans=1;
for(R i=2;i*i<=n;++i) if(n%i==0)
{
n/=i;
ans*=i-1;
while(n%i==0) n/=i,ans*=i;
}
if(n>1) ans*=n-1;
return ans;
}
int main()
{
scanf("%lld%lld",&a,&p);
printf("%lld\n",q_pow(a,phi(p)-1,p));
return 0;
}

 

如有错误,恳请您指正(我太菜了);如有不理解,可留言,我会尽量回复。。。(高中生(逃)。。)

by Jackpei 2019.2.13

版权声明
本文为[Jack_Pei]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/Jackpei/p/10372392.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领