乘法逆元介绍


  • 引入

    1、对于模意义下的运算,例如我们知道(a + b) % p = (a % p) + (b % p)或者(a * b) % p = (a % p) * (b % p)成立,但是对于模意义下的除法不成立(a / b) % p != (a % p) / (b % p)。不过,我们可以把模意义的除法转换成模意义的乘法
    2、举例探讨:(7 / 2) % 5 中,把除法转成乘法写作 (7 * (1/2)) % 5,再将分数写成幂的形式写作 (7 * 2-1) % 5
    3、由于取模运算结果一定是整数,所以 (7 * 2-1) % 5 结果一定是整数,即说明必定能把 2-1 这个分数转换成某个整数。所以,问题的关键就在于能转换成哪个整数
    4、这时便需要引入乘法逆元的概念了,它可以辅助我们完成模意义的除法模意义的乘法转换

  • 乘法逆元

    1、类比初中的倒数的概念:如果 a * b = 1,则 a 和 b 互为倒数。对于 (7 * 2-1) % 5 来说,其可以等价地写成 (7 * 3) % 5,这是因为在模 5 下,有 (3 * 2) % 5 = 1 成立。可以近似地理解成3 和 2模 5互为倒数,但这里实际不称作倒数,而称作乘法逆元
    2、因此,对于上面的例子,7 乘 (1/2) 模 5,就可以理解成7 乘 (2 的乘法逆元) 模 5,这样便可以转换成模意义的乘法得到结果。即被除数除以除数模 n,等同于被除数除数的乘法逆元模 n
    3、如何得到乘法逆元?例如求 (1/2) 在模 7 下的乘法逆元,就要看谁乘 2 模 7 等于 1,显然存在 (2 * 4) % 7 = 1,因此4 是 (1/2) 的乘法逆元,算式写作 2-1 mod 7 = 4。注意此时式子中 2-1 代表逆元而不是分数
    4、乘法逆元详细定义如下图。模运算下也会继承一些普通幂运算的性质,如下图的运算示例乘法逆元还有一些性质,如下图




求逆元-拓展欧几里得算法


  • 引入

    1、由于前面乘法逆元性质中提到,只有当gcd(a, n) = 1(即 a, n 互素,n 为模数)才有乘法逆元存在。先前介绍过拓展欧几里得算法,因为gcd(a, n) = 1,根据裴蜀定理一定有as + nt = gcd(a, n) = 1等式两边同时模 n,便得到 a*s 和 1 在模 n 下同余。易知,模 n 下 a 的乘法逆元是 s
    2、因此,要求乘法逆元时,就可以调用拓展欧几里得算法,把 a, n 当做参数传入,其返回的 s 即为所求。要得到最小的正整数乘法逆元inv[b],只需要处理一下 s:inv_b = (s % n + n) % n

  • 代码实现

    #include <iostream>
    using namespace std;
    
    int ex_gcd(int a, int b, int &s, int &t)
    {
        // s, t 表示 s_i 和 t_i,其默认值为 s_1 = 0 和 t_1 = 1
        // s_ 和 t_ 表示 s_i-1 和 t_i-1,其默认值表示 s_0 = 1 和 t_0 = 0
        int s_ = 1, t_ = 0, q, temp;
        while (a % b)
        {
            q = a / b;
    
            // 迭代公式:s_i+1 = s_i-1 - s_i * q_i
            temp = s;       // 记录当前 s_i
            s = s_ - s * q; // 计算 s_i+1
            s_ = temp;      // 下一轮 s_i
            // 迭代公式计算 t_i+1
            temp = t;
            t = t_ - t * q;
            t_ = temp;
    
            temp = a % b;
            a = b;
            b = temp;
        }
        return b;
    }
    
    int main()
    {
        // 求 (a / b) % n 的值,易证 s 为 b 的乘法逆元
        // s, t 表示 s_i 和 t_i,其默认值为 s_1 = 0 和 t_1 = 1
        int a, b, n, s = 0, t = 1;
        cin >> a >> b >> n;
    
        // 如果 b, n 互素,才有乘法逆元;算出 b 的乘法逆元,存入 s
        if (ex_gcd(b, n, s, t) == 1)
        {
            // 得到最小的正整数的乘法逆元
            int inv_b = (s % n + n) % n;
            // 被除数 除以 除数 再模 n,等同于 被除数 乘 除数的乘法逆元 再模 n
            // 对于模乘法,(a * b) % n = ((a % n) * (b % n)) % n
            cout << ((a % n) * (inv_b % n)) % n;
        }
        else
            cout << "Impossible";
        return 0;
    }

求逆元-快速幂 & 费马小定理


  • 引入

    1、费马小定理:若有整数 a, pp 为质数,则有 ap - a 是 p 的倍数,也可以表示为 ap 与 a 在模 p 下同余。如果 a 不是 p 的倍数的话,这个定理可描述为 ap-1 和 1 在模 p 下同余
    2、因为乘法逆元性质gcd(a, n) = 1(a, n 互素,n 为模数),满足 a 不是 n 的倍数。因此,当 n 为质数时(必须条件),一定有 an-1 和 1 在模 n 下同余,又因为乘法逆元定义中有 a*z 和 1 在模 n 下同余(z 为 a 的乘法逆元),因此得到 a*z 和 an-1 在模 n 下同余。两边同时除以 a,得到 z 和 an-2 在模 n 下同余
    3、因此,在 n 为质数的情况下(1e9 + 7 是常见的满足条件的模数),要求乘法逆元 z,只需要求 an-2 % n 的值,使用快速幂(幂取模)来计算即可

  • 代码实现

    #include <iostream>
    using namespace std;
    
    int gcd(int a, int b)
    {
        int temp;
        while (a % b)
        {
            temp = a;
            a = b;
            b = temp % b;
        }
        return b;
    }
    
    // 幂取模
    unsigned long long ModExp(int a, int n, int m)
    {
        unsigned long long result = 1;
        a %= m; // 对第一次的乘数 a 取模
    
        while (n)
        {
            if (n & 1)
                result = (result * a) % m; // 对结果取模,结果又是下一次运算的乘数之一
    
            a = (a * a) % m; // 对乘数 a 取模
            n >>= 1;
        }
    
        return result;
    }
    
    int main()
    {
        // 求 (a / b) % n 的值
        int a, b, n;
        cin >> a >> b >> n;
    
        // 如果 b, n 互素,才有乘法逆元;只有 n 为质数才可以用快速幂(is_prime细节省略)
        if (gcd(b, n) == 1 && is_prime(n))
        {
            // b 的乘法逆元
            int inv_b = ModExp(b, n - 2, n) % n;
            cout << ((a % n) * (inv_b % n)) % n;
        }
        else
            cout << "Impossible";
        return 0;
    }

求逆元-线性递推


  • 引入

    1、设有n = a * q + r(a, n 互素,n 为模数),必然有 aq + r 与 0 在模 n 下同余,且有q = n / ar = n % a
    2、令同余方程两边同乘 a-1 * r-1(即inv[a] * inv[r]),因为乘法逆元定义中有(a * inv[a]) % n = 1,所以方程可变为 q * inv[r] + inv[a] 与 0 在模 n 下同余,移项得到 inv[a] 与 -q * inv[r] 在模 n 下同余。把第一步得到的 q, n 的值带入,最终得到 inv[a] 与 -(n / a) * inv[n % a] 在模 n 下同余
    3、分析可得,同余方程右侧[n % a]一定小于方程左侧[a],这说明如果通过递推的方式求左侧值时,右侧的值都是已知的,只需要给出inv[0] = 0, inv[1] = 1(0 没有乘法逆元,1 的乘法逆元是 1)作为递推初始值即可。另外,右侧的有-(n / a)使得求得的左侧值可能是负值,因此需要转换成最小的正整数乘法逆元inv = (inv % n + n) % n
    4、因此,要求乘法逆元 z(z = inv[a]),可以通过递推式inv[a] = -n / a * inv[n % a]计算(其中inv[0] = 0, inv[1] = 1,每次计算后须转换为最小正整数乘法逆元)

  • 代码实现

    #include <iostream>
    using namespace std;
    
    // inv[0] = 0, inv[1] = 1
    int inv[1000001] = {0, 1};
    
    int gcd(int a, int b)
    {
        int temp;
        while (a % b)
        {
            temp = a;
            a = b;
            b = temp % b;
        }
        return b;
    }
    
    // 转换成最小正整数逆元
    int pos_mod(int a, int n)
    {
        return (a % n + n) % n;
    }
    
    // 递归计算乘法逆元
    int get_inv(int a, int n)
    {
        // 直到计算到 inv[a],可能是inv[0] 或 inv[1]
        if (inv[a])
            return inv[a];
        // 递推表达式,未知值继续递归
        inv[a] = pos_mod(-n / a * get_inv(n % a, n), n);
    
        return inv[a]; // 返回最后的结果
    }
    
    int main()
    {
        // 求 (a / b) % n 的值
        int a, b, n;
        cin >> a >> b >> n;
    
        // 如果 b, n 互素,才有乘法逆元
        if (gcd(b, n) == 1)
        {
            int inv_b = get_inv(b, n);
            cout << ((a % n) * (inv_b % n)) % n;
        }
        else
            cout << "Impossible";
        return 0;
    }

页底评论