例题 51nod1256题目链接

乘法逆元 ：

X*b=1(mod p)   x乘以b在模p的意义下恒等于1  那么 b就是x在mod p的情况下的逆元

意义

乘法逆元的一大应用是模意义下的除法，除法在模意义下并不是封闭的 所以我们可以根据乘法逆元，将 ( a / b ) % c   转化为   ( a * x ) % c  (x是a的逆元) 将其转化为乘法。

求法一：费马小定理

费马小定理：假如p是质数，且gcd(a,p)=1，那么 a的(p-1)次方 ≡ 1（mod p） 由费马小定理我们可以转化为     a的(p-2) 次方 * a 恒等于1(mod p)  那么a的p-2次方（mod p的情况下）就是 a的逆元 所以 我们求出a的（p-2）次方（mod p的情况）就行了   数字太大的话  可用快速幂求 注意 使用费马小定理必须在p是质数的情况下

求法二：扩展欧几里得定理

扩展欧几里得定理：若gcd(a,b)=1  则必存在 x y  使得 a*x+b*y=1 那么 求逆元的式子 X*B=1(mod p)  可以转化为  X*B=y*p+1  也就是  X*B-y*p=1 显然 这个式子和扩展欧几里得的式子一样  那么我们知道了 X p  就求出了 B y 注意 求出来的逆元B可能是负的  需要   (B+p)%p  再输出   下面是例题51nod1256的代码   #include #include #include #include using namespace std; int exgcd(int a,int b,int &x,int &y){ if(b==0){ x=1;y=0;return a; } int r=exgcd(b,a%b,x,y); int t=y; y=x-(a/b)*y; x=t; return r; } int main(){ int m,n,x,y; scanf("%d%d",&m,&n); exgcd(m,n,x,y); cout<<(x+n)%n; return 0; }