【筆記】模逆元

  • 模逆元 (modular multiplicative inverse)【參考
  • 或稱模倒數,或者模反元素。【Wiki
  • inv[i] = i 的逆元 (% mod)
    • 公式:inv[i]=  (mod / i) * inv[mod % i]
    • 為避免負數取模,inv[i]= mod – ( mod / i * inv[mod % i]) % mod
  • 【例子】mod = 17, inv[10] = 12
    • (10 * 12) % 17 = 1
  • 【例子】mod = 11, inv[3] = 4
    • (3 * 4) % 11 = 1
  • 【例子】mod = 1e9 + 7, inv[2] = 5e8 + 4
    • 2 * (5e8 + 4) = 1e9 + 8, (1e9+8) % (1e9+7) = 1
  • 【應用】可以用來快速計算 C(n, k) = n! / (k! * (n-k)!) = pre[n] * prei[k] * prei[n-k]
  • 【範例】AtCoder 154F – Many Many Paths 【題解
#include <iostream>
using namespace std;
#define ll long long

const int mod = 17, maxn = 20;

ll pre[maxn+1];
ll inv[maxn+1];
ll prei[maxn+1];

void build(int n){
    pre[1] = pre[0] = 1, inv[1] = inv[0] = 1, prei[1] = prei[0] = 1;
    for(int i = 2 ; i <= n ; i++){
        pre[i] = pre[i-1] * i % mod;
        // i 的逆元inv[i]= -(p/i) * inv[p%i] (mod p)
        inv[i] = mod - (mod / i * inv[mod % i]) % mod;
        prei[i] = prei[i-1] * inv[i] % mod;
    }
}

ll C(int n, int k){
   return pre[n] * prei[k] % mod * prei[n-k] % mod;
}

int main(){
    build(maxn);
    cout << inv[10] << endl;
    cout << C(6, 3) << endl;
}
分享本文 Share with friends