分数取模

分数取模以及快速幂

分数取模

定义：对于分数 $\frac{a}{b}$ ($a、b$互质)对 $x$ 取模,有 $c = \frac{a}{b}\ mod\ x$, 其中 $bc = a\ mod \ x$.

计算：
费马小定理：其中 $p$ 为质数, $a$ 不为 $p$ 倍数

$$
a^{p-1} = 1(mod \ p)
$$

则可以推出：

$$
a^{p-2}(mod\ p) = (a^{p-1}(mod\ p)*a^{-1}(mod\ p))(mod\ p) \ = a^{-1}(mod\ p)
$$

因此：

$$
\frac{a}{b} (mod\ p) = (a b^{-1})(mod\ p) \ = (a (mod\ p) * b^{-1} (mod\ p))(mod\ p) \ = (a (mod\ p) * b^{p-2} (mod\ p))(mod\ p)
$$

主要计算 $b^{p-2}(mod\ p)$, 可用快速幂计算：

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

分数取模计算如下：

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

• 本文作者： JiXiaw
• 本文链接： http://jixiaw.github.io/2020/08/29/mod/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！