分数取模

前置知识

乘法逆元

原理

定义

计算

代码实现

long long fastPow(long long a, long long k, long long p){  // a 底数， k 指数， 求 a^k mod p
    long long res = 1;
    a%=p;
    while(k > 0){
        if (k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

long long fractionMod(long long a, long long b, long long p){  // a/b mod p
    return ((a % p) * fastPow(b, p-2, p)) % p;
}