转载

乘法逆元

同余方程$ax/equiv 1(mod/ n)$，$gcd(a,n)=1$时有整数解。这时称求出的$x$为$a$对模$n$的乘法逆元

其实乘法逆元就是一类特殊的同余方程求解，普通的同余方程是$ax/equiv b(mod/ n)$，乘法逆元的其实就是当$b=1$时的解$x$

由$ax/equiv 1(mod/ n)$得：

ax = ny_1 + p//

1 = ny_2 + p

两式相减$ax-1=n(y_1-y_2)$，移项$ax+ny=1$，所以求乘法逆元也就转换为了求裴蜀方程$ax+ny=1$的解

关于裴蜀方程求解，可以看我的裴蜀等式与扩展欧几里得算法这篇文章

import java.util.Scanner;

public class Main {
    static long x, y;
    static long exgcd(long a, long b) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        long res = exgcd(b, a % b);
        long x1 = x;
        x = y;
        y = x1 - (a / b) * y;
        return res;
    }

    static long linearEquation(long a, long b, long m) throws Exception {
        long d = exgcd(a, b);
        if (m % d != 0)
            throw new Exception("Impossible");
        long n = m / d;
        x *= n;
        y *= n;
        return d;
    }
    
    static long inverseElement(long a, long b) throws Exception {
        long d = linearEquation(a, b, 1);
        x = (x % b + b) % b; // 保证x>0
        return d;
    }
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        try {
            inverseElement(13, 5);
            System.out.println(x);
        } catch (Exception e) {
            System.out.println("Impossible");
        }
    }
}

例题： HDU1576

原文 https://www.wmathor.com/index.php/archives/1220/

正文到此结束