分数取模

· · 个人记录

求：

\frac{a}{b}\operatorname{mod} p

解：

由费马小定理

a^p\equiv a(\operatorname{mod}p)

可得

a^{p-2}\equiv a^{-1}(\operatorname{mod} p)

则

\frac{a}{b}\operatorname{mod}p=a\times b^{-1}\operatorname{mod}p=a\times b^{p-2}\operatorname{mod}p

即

\frac{a}{b}\equiv a\times b^{p-2}(\operatorname{mod}p)

附赠代码：

快速幂

const long long mod = 998244353;
inline long long pow(long long x, long long k){
    long long res = 1;
    while(k) {
        if(k&1) res = res * x % mod;
        x = x * x % mod;
        k >>= 1;
    }
    return res;
}

求x^{-1}\mod p

inline long long inv(long long x, long long p){return pow(x, p-2);}

实例

#include <iostream>
using namespace std;
const long long mod = 998244353;
inline long long pow(long long x, long long k){
    long long res = 1;
    while(k) {
        if(k&1) res = res * x % mod;
        x = x * x % mod;
        k >>= 1;
    }
    return res;
}
inline long long inv(long long x){return pow(x, mod-2);}

int main(){
    cout << 5 * inv(4) % mod;
    return 0;
}

上面的代码输出是748683266，即\frac{5}{4}\mod 998244353的值。

因为748683266\times 4\mod 998244353=5，而\frac{5}{4}\times 4 \mod 998244353 =5，所以：

\frac{5}{4}\equiv748683266(\operatorname{mod}p)

所以说748683266是\frac{5}{4}取模的结果。