有理数取模-分数取模-费马小定理

整数取模好运算, 但是分数怎么取模呢?

• 假设求 , 等价于求
• 由费马小定理
  *
  
  

参考代码

public class Mod {

    public static final long MOD = 1_000_000_007;

    /**
     * 模乘
     * @param x
     * @param y
     * @return x * y % MOD
     */
    public static long mul(long x, long y) {
        return ((x % MOD) * (y % MOD)) % MOD;
    }

    /**
     * 模加
     * @param x
     * @param y
     * @return (x + y) % MOD
     */
    public static long add(long x, long y) {
        return  ((x % MOD) + (y % MOD)) % MOD;
    }

    /**
     * 模快速幂
     * @param x
     * @param n
     * @return x^n % MOD
     */
    public static long quickPower(long x, long n) {
        if (n == 0) return 1;
        if (n == 1) return x % MOD;
        long tmp = quickPower(x, n >> 1);
        return (n & 1) == 0 ? mul(tmp, tmp) : mul(x, mul(tmp, tmp));
    }

    /**
     * 分数求模
     * 费马小定理 a^(p-1) mod p = 1 mod p
     * a * a^(p-2) mod p = 1 mod p
     * a^(p-2) mod p = a^(-1) mod p
     * (b/a) % p = b * a^(-1) % p = b * a^(p-2) % p
     * @param a 分母
     * @param b 分子
     * @return (b/a) % MOD
     */
    public static long fractionMod(long a, long b) {
        return mul(b, quickPower(a, MOD-2));
    }

}