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

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

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

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

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

(就不介绍了（逃）)

下面我们来说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是素数时，φ(p)=(p-1)·φ(p)，因为有(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