乘法逆元小结

在求解除法取模问题 (a/b)%m 时，我们可以转化为 (a%(b∗m))/b ， 

但是如果b很大，则会出现爆精度问题，所以我们避免使用除法直接计算。 

可以使用逆元将除法转换为乘法： 

假设b存在乘法逆元，即与m互质（充要条件）。设c是b的逆元，即 b∗c≡1(modm) ，那么有 a/b=(a/b)∗1=(a/b)∗b∗c=a∗c(modm)  

即，除以一个数取模等于乘以这个数的逆元取模。

1. 逆元求解一般利用扩欧。
2. 当 m 为质数的时候直接使用费马小定理，m非质数使用欧拉函数。
3. 当 m 为质数的时候，神奇的线性方法。

扩展欧几里得算法：

要求 a,m 互素。存在唯一解。 

之前总结过扩展欧几里得算法

代码：

int extgcd(int a, int b, int& x, int& y)
{
    int d = a;
    if(b != ){
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }else {
        x = ;
        y = ;
    }
    return d;
}
int mod_inverse(int a, int m)
{
    int x, y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}           

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18

费马小定理：

在 p 是素数的情况下，对任意整数 x 都有 xp≡x(mod)p 。 

如果 x 无法被 p 整除，则有 xp−1≡1(modp) 。 

可以在 p 为素数的情况下求出一个数的逆元， x∗xp−2≡1(modp) ， xp−2 即为逆元。

代码：

利用快速幂求出逆元。           

• 1

• 1

欧拉函数：

令 ϕ(m) 表示小于等于 m 且与 m 互素的正整数的个数。 

如果 x 和 m 互质，则有 xϕ(m)≡1(modm) ，即 x×xϕ(m)−1≡1(modm) ， xϕ(m)−1 即为 x 的逆元。 

在 m 为质数的情况下， ϕ(m)=m−1 ，即为费马小定理。

代码：

关键是求出欧拉函数的值。 

利用欧拉函数的积性性质：

对于任意整数 n ，可以将它分解 n=pk11∗pk22∗pk33...pkmm ，其中 pi 为质数。

其中 ϕ(n)=ϕ(p1k1)∗ϕ(pk22)...ϕ(pkmm)

最后转化为 ϕ(n)=n∗∏(pi−1)/pi

对给定n进行整数分解。时间复杂度 O(n√) 。

int eurler_phi(int n)
{
    int res = n;
    for(int i = ; i * i <= n; i++){
        if(n % i == ){
            res = res / i * (i - );
            while(n % i == ) n /= i;
        }
    }
    if(n != ) res = res / n * (n - );
    return res;
}           

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12

筛法求欧拉函数值的表，利用埃氏筛法，每次发现质因子就把他的倍数的欧拉函数乘上 (p−1)∗p 。 

如ACdreamers博客里介绍，利用定理进行优化 

【update】这个定理是有用的，但是个人觉得他对偶数预处理的写法并没有啥用

当n为奇数时，有 ϕ(2n)=ϕ(n)

因为2n是偶数，偶数与偶数一定不互素，所以只考虑2n与小于它的奇数互素的情况，则恰好就等于n的欧拉函数值。

int euler[maxn];
void euler_phi2()
{
    for(int i = ; i < maxn; i++)  euler[i] = i;
    for(int i = ; i < maxn; ++i){
        if(euler[i] == i){
            for(int j = i; j < maxn; j += i){
                euler[j] = euler[j] / i * (i - );
            }
        }
    }
}                                
我们要在线性时间内求出
    
     1−1,2−1…,(p−1)−1(modp)
     

     
      p为质数
      


 
  
   
    1∗1≡1(modp)⇒1−1≡1(modp)
   
 

 
  
   
    a∗a−1≡1(modp)    1<a<p
   
 
令
   
    k=⌊pa⌋，r=p  mod  a
    

 
  
   
    p=k∗a+r       0<r<ak∗a+r≡0(modp)(k∗a+r)∗a−1∗r−1≡0(modp)k∗r−1+a−1≡0(modp)a−1≡−k∗r−1(modp)a−1=−⌊pa⌋∗(p  mod  a)−1  mod  p=(p−⌊pa⌋)∗(p  mod  a)−1  mod  p
   
 

       
inv[]=;
for(int i=;i<=n;i++)
    inv[i]=(p-p/i)*inv[p%i]%p;           
   

• 1
• 2
• 3

• 1
• 2
• 3

同时，也可以据此来递归求出逆元，每次时间复杂度为 O(log2n)

int Get_inv(int n){
    if(n==)
        return ;
    return (p-p/n)*(Get_inv(p%n))%p;
}           

• 1
• 2
• 3
• 4
• 5

• 1
• 2
• 3
• 4
• 5

递归的时候p也必须为质数  

一组例子,n=7,p=18

人一我百！人十我万！永不放弃~~~怀着自信的心，去追逐梦想