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]) 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 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 分类: 数论https://www.cnblogs.com/Jackpei/p/10372392.html