乘法逆元

同余方程 $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