乘法逆元+模的运算规则

模的运算规则

运算规则

模运算与基本四则运算有些相似，但是除法例外。其规则如下：
a + b) % p = a % p + b % p) % p （1）
a – b) % p = a % p – b % p) % p （2）
a * b) % p = a % p * b % p) % p （3）
a^b) % p = a % p)^b) % p （4）

%运算法则 

1. a*b) %p= a%p) *b%p) 乘法的

2. a/b) %p= a *b^-1)%p) 除法的

结合律：
a+b) % p + c) % p = a + b+c) % p) % p （5）
a*b) % p * c)% p = a * b*c) % p （6）// a%p*b)%p=a*b)%p
交换律：
a + b) % p = b+a) % p （7）
a * b) % p = b * a) % p （8）
分配律：
a +b)% p * c) % p = a * c) % p + b * c) % p) % p （9）
重要定理：
若a≡b % p)，则对于任意的c，都有a + c) ≡ b + c) %p)；（10）
若a≡b % p)，则对于任意的c，都有a * c) ≡ b * c) %p)；（11）
若a≡b % p)，c≡d % p)，则 a + c) ≡ b + d) %p)，a – c) ≡ b – d) %p)，
a * c) ≡ b * d) %p)，a / c) ≡ b / d) %p)； （12）

 
乘法逆元：
定义： 满足a*k≡1 mod p)的k值就是a关于p的乘法逆元。
为什么要有乘法逆元呢？
当我们要求（a/b） mod p的值，且a很大，无法直接求得a/b的值时，我们就要用到乘法逆元。 我们可以通过求b关于p的乘法逆元k，将a乘上k再模p，
即a*k) mod p。其结果与a/b) mod p等价。
证：（其实很简单。。。）  根据b*k≡1 mod p)有b*k=p*x+1。 k=p*x+1)/b。 
把k代入a*k) mod p，得：
a*p*x+1)/b) mod p  =a*p*x)/b+a/b) mod p 
=[a*p*x)/b) mod p +a/b)] mod p 
=[p*a*x)/b) mod p +a/b)] mod p 
//p*[a*x)/b] mod p=0
所以原式等于：a/b) mod p
 
 应用请看POJ1845的解析：
 
（a^k-1）/x)%mod=a%mod)^k -1)%mod)*x^-1)%mod;
不知道这个公式是否成立，先这么用着了。。。。。orz
 
 转载：

在计算一个很大的组合数modP时会用到乘法逆元。即把/a变成*fa))，其中fa)为a在模P意义下的乘法逆元，即a*fa) mod P=1
计算乘法逆元有两种方法，扩展gcd或基于欧拉公式的快速幂取模。
------------------------------------------------------------------------------------------------------
扩展gcd就是求解方程ax=1mod P)的最小整数解.
设ax=1+y*p，即a*fa,p)=1+p*ga,p)，把x和y的解看成关于a,p的函数。
a>=p时，设a=p*k+r，则式子变成：
p*k*fa,p)+r*fa,p)=1+p*ga,p)，移项，得r*fa,p)=1+p*ga,p)-k*fa,p))
那么就得到fa mod p,p)=fa,p)，ga mod p,p)=ga,p)-[a/p]*fa,p);
p>=a时差不多一个意思。
所以把f,g设成全局变量，像普通gcd那样做，即时更新f,g即可。
----------------------------------------------------------------------------------------------------
设欧拉函数phix)=在[1,x-1]中与x互质的数字个数。那么欧拉公式：
a^phiP)=1mod P)
两边同除a,即可得到a^phiP)-1) mod P即为a在模P意义下的乘法逆元。
特例：

如果P是质数，那么phiP)=P-1.即a的乘法逆元为a^P-2)，快速幂即可。

#include <iostream>
using namespace std;
int extended_gcdint a,int b, int &x, int &y)
{
    if b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    else
    {
        int gcd = extended_gcdb, a % b, x, y);
        int t=x%mod;
        x=y%mod;
        y=t-a/b*x)%mod+mod)%mod;
        return gcd;
    }
}
int main)
{
    int i, x, y;
    const int P = 13;
    for i = 1; i < P; ++i)
    {
        extended_gcdi, P, x, y);
        while x < 0) x += P;
        printf"1 div %d = %d
", i, x);
    }
    return 0;
}