使用欧拉定理求逆元

欧拉函数

欧拉函数φ(n)(n∈N*)是小于等于n的正整数中与n互质的数的个数。

欧拉定理

对于任意互素的a和n,有

所以可以通过快速幂和欧拉函数来求逆元

欧拉函数模板

public static long euler(long n) {
    long res = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            res = res / i * (i - 1);
        }
        while (n % i == 0) {
            n /= i;
        }
    }
    if (n > 1) {
        res = res / n * (n - 1);
    }
    return res;
}

快速幂模板

public static long fastPow(long a, long b, long mod) {
    long res = 1;
    while (b > 0) {
        if (b % 2 == 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

AC代码

import java.util.Scanner;

public class Main {
    public static long euler(long n) {
        long res = n;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                res = res / i * (i - 1);
            }
            while (n % i == 0)
                n /= i;
        }
        if (n > 1) {
            res = res / n * (n - 1);
        }
        return res;
    }

    public static long fastPow(long a, long b, long mod) {
        long res = 1;
        while (b > 0) {
            if (b % 2 == 1) {
                res = res * a % mod;
            }
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        System.out.println(fastPow(a, euler(b) - 1, b));
    }
}