# 【筆記】模逆元

• 模逆元 (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;
}
```