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] <=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#include #include #define R register int#define ll long longusing 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