乘法逆元
(由于打不出来三横的同余符号，下面的同余符号都用两横的代替)
乘法逆元是什么？
说得简单一点，就是有两个数 a , b,有a*b=1(mod p)
a就是b的乘法逆元，当然是关于模数p的。显然我们得到b也是a的乘法逆元。
（直接看，估计是看不出来的，但是我们有两位牛人）
先介绍一种求法：
先由费马小定理，有：（p为素数这个条件很重要）
m^(p-1)=1(mod p)
两边同时除以m，有
m^(p-2)=m^(-1) (mod p)
而m^(-1)其实就是m的逆；
所以m对于mod p的逆，就是m^(p-2);
所以，只需要求出m^(p-2)就可以了。
那求次方，就只需要用快速幂取模运算就可以了。
再介绍一种算法：
直接用拓展欧几里得求逆元。
其实很简单。
现在有一个定理：（其实叫裴蜀定理：裴蜀定理（贝祖定理））
m,n均为整数，那么一定存在整数x,y使得mx+ny=gcd（m,n）
(其中gcd表示最大公约数)
特别地，如果(m,n)=1，那么一定存在整数x,y,使得mx+ny=1；
号的，那么我们把x，y解出来，发现：
x是m%n的逆元；y是n%m的逆元。
用拓展欧几里得来解出这个方程就可以了。
（具体的程序代码待会会有）
......../
下面给出函数代码：
这个是快速幂：
long long Pow(long long a,long long n)
{
int tt=a;
int ans=1;
while(n!=0)
{
if(n%2==1)
ans*=tt;
tt=tt*tt;
n/=2;
}
return ans;
}
然后求出a^(p-2)就可以了；
然后就是
#define LL long long
LL exgcd(LL a, LL b, LL &x, LL &y)
{//拓展gcd求逆元
LL t, ret;
if (b == 0) {
x = 1, y = 0;
return a;
}
ret = exgcd(b, a%b, x, y);
t = x, x = y, y = t - a / b*y;
return ret;
}
若有问题，欢迎讨论。 | 
转播
