今天我们来探讨逆元在 ACM-ICPC 竞赛中的应用，逆元是一个很重要的概念，必须学会使用它。

 

对于正整数和，如果有，那么把这个同余方程中的最小正整数解叫做模的逆元。

 

逆元一般用扩展欧几里得算法来求得，如果为素数，那么还可以根据费马小定理得到逆元为。

 

推导过程如下

                            

 

求现在来看一个逆元最常见问题，求如下表达式的值（已知）

 

           

 

当然这个经典的问题有很多方法，最常见的就是扩展欧几里得，如果是素数，还可以用费马小定理。

 

但是你会发现费马小定理和扩展欧几里得算法求逆元是有局限性的，它们都会要求与互素。实际上我们还有一

种通用的求逆元方法，适合所有情况。公式如下

 

          

 

现在我们来证明它，已知，证明步骤如下

 

          

 



逆元公式：

 

                     

 

因为可能会很大，超过int范围，所以在快速幂时要二分乘法。

 


其实有些题需要用到模的所有逆元，这里为奇质数。那么如果用快速幂求时间复杂度为，

如果对于一个1000000级别的素数，这样做的时间复杂度是很高了。实际上有的算法，有一个递推式如下

 

                   

 

它的推导过程如下，设，那么

 

       

 

对上式两边同时除，进一步得到

 

       

 

再把和替换掉，最终得到

 

       

 

初始化，这样就可以通过递推法求出模奇素数的所有逆元了。

 

另外模的所有逆元值对应中所有的数，比如，那么对应的逆元是。

 


逆元：

定义 对a∈Zm，存在b∈Zm，使得a+b ≡ 0 (mod m)，则b是a的加法逆元，记b= - a。
定义 对a∈Zm，存在b∈Zm，使得a×b ≡1 (mod m)，则称b为a的乘法逆元。
我们通常所指的是乘法逆元。

然而乘法逆元的应用也需要条件:

对于乘法逆元：在mod m的操作下（即Zm中），a存在乘法逆元当且仅当a与m互质。不定方程ab+mx=1的任意一组整数解(b,x)，b就是a的乘法逆元。具体计算可以使用扩展欧几里德算法(Extended-GCD)。

kuangbin神给的模板

[cpp] view plain copy
  1. //返回d=gcd(a,b);和对应于等式ax+by=d中的x,y  
  2. long long extend_gcd(long long a,long long b,long long &x,long long &y)  
  3. {  
  4.     if(a==0&&b==0) return -1;//无最大公约数  
  5.     if(b==0){x=1;y=0;return a;}  
  6.     long long d=extend_gcd(b,a%b,y,x);  
  7.     y-=a/b*x;  
  8.     return d;  
  9. }  
  10. //*********求逆元素*******************  
  11. //ax = 1(mod n)  
  12. long long mod_reverse(long long a,long long n)  
  13. {  
  14.     long long x,y;  
  15.     long long d=extend_gcd(a,n,x,y);  
  16.     if(d==1) return (x%n+n)%n;  
  17.     else return -1;  
  18. }  

以下两种写法都必须要求MOD为素数


1.#define Inv(x)  (Pow(x,MOD-2))

由x^(m-1) ≡ 1 (mod m)(费马小定理)

故 x* x^(m-2)≡ 1 (mod m),显然x对模m的逆元是x^(m-2)

2.还有一种写法(来源)

可以O(n)时间求逆

[cpp] view plain copy
  1. int[] inv = new int[MAXN];  
  2. inv[1] = 1;  
  3. for (int i = 2; i<MAXN; i++)  
  4.     inv[i] = inv[MOD%i]*(MOD-MOD/i)%MOD;  
再贴一个快速幂的模板：

[cpp]  view plain  copy
  在CODE上查看代码片 派生到我的代码片
  1. // m^n % k  
  2. long long quickpow(long long m,long long n,long long k)  
  3. {  
  4.     long long b = 1;  
  5.     while (n > 0)  
  6.     {  
  7.           if (n & 1)  
  8.              b = (b*m)%k;  
  9.           n = n >> 1 ;  
  10.           m = (m*m)%k;  
  11.     }  
  12.     return b;  
  13. }   


 

贴一个关于逆元的链接：http://blog.csdn.net/cqlf__/article/details/7953039