逆元：已知P为质数，且gcd(A,P)==1,  A*B在同模P的情况下与1相等 求出B的值即 A*B=1(在mod P的条件下)所以乘B即乘以A^-1 ，B就是A的逆元
费马小定理：P为质数时且gcd(A,P)==1,则A^(P-1)=1(在mod P的条件下)证明我不会qwq所以根据费马小定理  A*B=A^(P-1) 所以B=A^(P-2)根据上述就可以轻松得到   A当P为质数且gcd(A,P)==1时的逆元例题：洛谷3381的模板题(用费马小定理只能得到83，会TLE一个点）

题目描述

给定n,p求1~n中所有整数在模p意义下的乘法逆元。

输入输出格式

输入格式：
一行n,p输出格式：
n行,第i行表示i在模p意义下的逆元。因为P为质数且A//费马小定理求逆元 #include using namespace std; int n,Mod; inline int Pow(int x,int y,int p){ int res=1; while(y){ if(y&1) res=(1LL*res*x)%p; y>>=1; x=(1LL*x*x)%p; }return res; }//快速幂 int main(){ scanf("%d%d",&n,&Mod); for(int i=1;i<=n;i++){ printf("%d ",Pow(i,Mod-2,Mod));//直接输出i^(Mod-2)%Mod,是不是很方便 } }