逆元

 

逆元

一、什么是逆元

  当求解公式:(a/b)%m 时,因b可能会过大,会出现爆精度的情况,所以需变除法为乘法:

  设c是b的逆元,则有b*c≡1(mod m);

  则(a/b)%m = (a/b)*1%m = (a/b)*b*c%m = a*c(mod m);

  即a/b的模等于a*b的逆元的模;

  逆元就是这样应用的;

 

二、求逆元的方法

  那么逆元怎么求 ? 首先这里得纠正一点, 我们不能直接说一个数的逆元是多少, 
应该这么说: 一个数 x 在模 p的条件下的逆元是多少.(这点概念还是蛮重要的) 
其次,我们不难得知一个数的逆元有无穷多个,但是我们只需要求得一个数的最小正整数逆元就行了

  另外,一个数 x 在模 p 的条件下不一定有逆元, x关于 p 的逆元存在 当且仅当 x 和 p 互质 
这里有一个推导: (设 a 为 x的逆元, b 为任意整数)

  x∗a≡1(mod p)= 将p连入式子=> x∗a=1−b∗p => x∗a+b∗p=1

  那么我们就得到了一组新方程: x∗a+b∗p=1 若x 和 p不互质, 则 x和 p 存在公约数 d=gcd(x,p)>1

  提取出d, 得到: d(x/d∗a+p/d∗b)=1 移项得到: (x/d∗a+p/d∗b)=1/d

  易知 x , p 能整除 d, 所以括号内定为整数, 又因为d>1 ,等式右边必为真分数, 等式无解

  证毕

  (1).费马小定理(证明)

  内容:费马小定理(Fermat's little theorem)是数论中的一个重要定理,在1636年提出。如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1(mod p)。 

  在是素数的情况下,对任意整数都有。 
  如果无法被整除,则有。 
  可以在为素数的情况下求出一个数的逆元,,即为逆元。

  题目中的数据范围1<=x<=10^9,p=1000000007,p是素数;

  所以x肯定就无法被p整除啊,所以最后就得出x^(p-2)为x的逆元啦。

  复杂度O(logn);

  x % p 中x的逆元为 quick_pow(x,p-2,p) x,y,mod (p是一个质数,而整数a不是p的倍数)

  (2)扩展欧几里得算法求逆元

  扩展欧几里得算法可以参考小白书;

  百度百科-乘法逆元中有这样一个例子:

  例如:4关于1模7的乘法逆元为多少?   4X≡1 mod 7   这个方程等价于求一个X和K,满足   4X=7K+1   其中X和K都是整数。

  求x,k就是扩展欧几里得算法了吧~

  可扩展欧几里得求逆元ax≡1(mod n)其中a,n互质;

  复杂度:O(logn);

  x % p 中x的逆元 先扩欧计算出x值,ex_gcd(a,p,inv_a,y),逆元则为inv_a 

  (3) 求 1! ~ n! 的逆元

    公式:inv[i]≡inv[i+1]?(i+1)(mod p)(inv[i]代表i!的逆元)

    fac[i]∗inv[i]≡1(mod p)

    fac[i+1]∗inv[i+1]≡1(mod p)=>fac[i]∗(i+1)∗inv[i+1]≡1(mod p)

    由 同余的除法原理可得 : inv[i]≡inv[i+1]∗(i+1)

    推导完毕

 

  (4) 逆元线性筛 ( P为质数 )

    求1,2,...,N关于P的逆元(P为质数)

    公式:inv[i]≡inv[p%i]∗(−p/i)(mod p)

    令 s=p/i,t=p%i, 则有:

    s∗i+t=p (显然)

    然后 s∗i+t≡0(mod p)

    移项得 t≡−s∗i(mod p)

    同除以 t∗i得t/(t∗i)≡−s∗i/(t∗i)(mod p)

    将除法转化为乘法 => inv[i]≡−s∗inv[t](mod p)

    于是将 s=p/i,t=p%i带入就可以得到: inv[i]≡inv[p%i]∗(−p/i)(mod p)

    推导完毕

    复杂度:O(N)

相关文章:

  https://blog.csdn.net/qq_35416331/article/details/81059747

  https://blog.csdn.net/tobeyours/article/details/79619333

   

 

逆元

上一篇:codeforces 997C Sky full of stars


下一篇:任意模数 NTT