模的运算规则 运算规则模运算与基本四则运算有些相似,但是除法例外。其规则如下: (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 ((a^k-1)/x)%mod=((((a%mod)^k -1)%mod)*x^-1)%mod; 不知道这个公式是否成立,先这么用着了。。。。。orz 转载: 在计算一个很大的组合数modP时会用到乘法逆元。即把/a变成*(f(a)),其中f(a)为a在模P意义下的乘法逆元,即a*f(a) mod P=1计算乘法逆元有两种方法,扩展gcd或基于欧拉公式的快速幂取模。------------------------------------------------------------------------------------------------------扩展gcd就是求解方程ax=1(mod P)的最小整数解.设ax=1+y*p,即a*f(a,p)=1+p*g(a,p),把x和y的解看成关于a,p的函数。a>=p时,设a=p*k+r,则式子变成:p*k*f(a,p)+r*f(a,p)=1+p*g(a,p),移项,得r*f(a,p)=1+p*(g(a,p)-k*f(a,p))那么就得到f(a mod p,p)=f(a,p),g(a mod p,p)=g(a,p)-[a/p]*f(a,p);p>=a时差不多一个意思。所以把f,g设成全局变量,像普通gcd那样做,即时更新f,g即可。----------------------------------------------------------------------------------------------------设欧拉函数phi(x)=在[1,x-1]中与x互质的数字个数。那么欧拉公式:a^phi(P)=1(mod P)两边同除a,即可得到a^(phi(P)-1) mod P即为a在模P意义下的乘法逆元。特例: 如果P是质数,那么phi(P)=P-1.即a的乘法逆元为a^(P-2),快速幂即可。
#include
|
|