从零到花式求解逆元

数论逆元知识总结.

逆元是求解 \(a / b \quad mod \quad c\)问题的知识，为什么会存在这个以及如何求解逆元呢？今天，本文将带着读者走进逆元；

上篇中国剩余写了好久，这篇就简略点，，一些证明就不写了，， 首先让我们加入带余除法的概念；

带余除法

a / b == c···d； a/b取整 [a / b] == c; a % b == d;

相关性质： (a + b) % c == (a % c + b % c) % c; (a - b) % c == (a % c - b % c) % c; (a * b) % c == (a % c * b % c) % c;

相关证明: a = dc + e, b = fc + g;

(a + b) % c == [(d + f)c + e + f] % c == (e + f) % c == (a % c + b % c) % c；

同理， 读者可自行证明其他定理；

那么问题来了，能不能除呢？？

通过举个例子我们便能知道会出现错误；

既然能加减，能乘，怎么能不能除？？

逆元

(a / b) % m不能展开，那么我们找到$b ^ {-1} $, 通过能乘的性质，就能得到(a % m * b ^{-1} % m) % m了，这个b^-1就是我们所求的逆元了，他要满足 \(b * b ^ {-1} \equiv 1 (mod m)\);

费马小定理求乘法逆元

当p为素数， \(p ^ {m - 1} \equiv 1 (mod \quad m)\);

代码实现： 

1
2
3
inline int solve (int a, int p) {
 return pow(a, p-2);
}

也可用快速幂求解； 代码实现： 

1
2
3
4
5
6
inline ll solve(ll a, ll p) {
    ll t = p - 2;
    long long ans = 1;
    for (a %= p; t; a = a * a % p, t >>= 1) if (t & 1) ans = ans * a % p;
    return ans;
}

欧拉定理求乘法逆元

欧拉函数φ(n)的值为小于等于n中与n构成互质关系的数的数量

欧拉定理即为\(a ^ { φ(n) } \equiv 1 (mod \quad m)\)

积性函数

为了求欧拉函数，我们先要了解一下积性函数，因为欧拉函数就是一个积性函数

积性函数的定义为当f(n)不恒为0时， (m, n) == 1时， f(nm) == f(m) * f(n); 若没有(m, n) == 1也满足，则为完全积性函数；

##求解欧拉函数

当p为素数， φ(p) = p - 1；

很好理解这一点，只有1不和素数互质； 但当n不为素数的时候呢？

当n为p ^ k时，只有p的倍数不与n构成互质， 也就是有p ^ k / p个数与n不构成互质， 那么\(φ(n) = p ^ k - p ^ {k - 1}\);

我们把n转化为$ n = p_1^{k_1} * p_2 ^ {k_2} * ... * p_m ^ {k_m} $ 根据积性函数的性质 得到$φ(n) = (p_1 ^ {k_1} - p_1 ^ {k_1 - 1}) * ... *(p_m ^ {k_m} - p_m ^ {k_m - 1}) $

再提取下公因数，得到$φ(n) = n * (1 - p_1 ^ {- 1} ) * (1 - p_2 ^ {- 1} ) * ... * (1 - p_m ^ {- 1} ) $

代码实现： 

1
2
3
4
5
6
7
8
9
10
inline int eurle(){
    p[1] = 1;
    for(int i = 2; i < Ma; i++){
        if(p[i])continue;
        for(int j = i; j < Ma; j += i){
            if(!p[i])p[i] = j;
            p[i] = p[i] / i * (i - 1);
        }
    }
}

接着用欧拉定理求逆元；

代码实现： 

1
2
3
int solve (int a, int m) {
 return pow(a, phi(m)-2);
}

也可用快速幂求解，参考费马小定理； 我们回去看费马小定理的时候，就发现这不就是欧拉定理的数为素数的时候吗？？查阅资料后，发现果然是欧拉证明的费马小定理；

扩展欧几里得求逆元

将\(b * b ^ {-1} \equiv 1 (mod m)\)转化为b * b^-1 + mk = 1; 便可用扩展欧几里得求解；

递推法求解逆元

其实也能通过递推打表解决；

设p = k * i + r;

k * i + r = 0 (mod p);

同时乘\(i^{-1} * r ^ {-1}\);

\(k * r^{-1} + i^{-1} ≡ 0 (mod p)\)

\(i ^ -1 ≡ -k * r ^ {-1} (mod p)\)

\(i ^ -1 ≡ -⌊p / i⌋ * (p mod i)^{-1} (mod p)\);

代码实现： 

1
2
3
ny[1] = 1;
for(int i = 2; i < Ma; i++)
    ny[i] = ((-(p / i) * ny[m % i]) % m + m) % m;

Comments

⬆︎TOP