费马小定理和逆元

费马小定理

若 为素数，，则 。

逆元

引入

我们知道，在实数域中，一个数 a 的倒数是 a⁻¹，因为 a * a⁻¹ = 1。除以一个数 b 就等价于乘以 b 的倒数，即 a / b = a * (b⁻¹)。

在模运算的世界里，我们想做类似的事情。对于一个整数 a 和一个模数 p，我们想找到一个整数 x，使得 (a * x) % p = 1。如果找到了这样的 x，我们就称 x 是 a 在模 p 意义下的 乘法逆元，记作 a⁻¹。

有了逆元，我们就可以在模 p 的意义下做除法了： (a / b) % p 就变成了 (a * b⁻¹) % p

重要前提：a 在模 p 意义下存在逆元的充要条件是 a 和 p 互质，即 gcd(a, p) = 1。

定义

若 ，则称 为 的逆元

当且仅当 时，逆元存在。

快速幂法

要求 为 素数

根据费马小定理，。

则 ，即 为 的逆元

ll mod;

ll quick_power(ll a, ll k) {
    ll res = 1;
    while (k) {
        if (k & 1)
            res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}

inline ll inv(ll x) {
    return quick_power(x, mod-2);
}

线性方法

记 inv[i] 为 的逆元。

即 inv[i] = (p - p / i) * inv[p % i] % p

ll mod;
ll inv[MAXN];

void init(){
    inv[1] = 1;
    for (int i = 2; i <= mod; ++i)
        inv[i] = (mod - mod / i) * inv[mod % i] % p;
}

性质

设 为 的逆元，则

卢卡斯定理

要求 为 素数

对于素数 ，有

即

ll mod;
ll fact[MAX_MOD];  // 阶乘
ll inv(int x);     // 逆元

ll C(ll m, ll n) {
    if (m > mod || n > mod)
        return C(m / mod, n / mod) * C(m % mod, n % mod) % mod;
    return fact[n] * inv(fact[m]) * inv(fact[n - m]) % mod;
}