若$a * x \equiv 1 \pmod b$，且$a$与$b$互质，那么我们就能定义: $x$ 为 $a$ 的逆元，记为$a^{-1}$，所以我们也可以称 $x$ 为 $a$ 在$\mod b$ 意义下的倒数，

所以对于 $\frac{a}{b} \pmod p$ ，我们就可以求出 $b$ 在 $\mod p$ 下的逆元，然后乘上 $a$ ，再 $\mod p$，就是这个分数的值了。

求解逆元

拓展欧几里得

// a*x+b*y = d
void ex_gcd(ll a, ll b, ll* d, ll* x, ll* y) {
	if (b == 0) {
		*d = a;
		*x = 1;
		*y = 0;
	}
	else {
		ex_gcd(b, a%b, d, x, y);
		ll t = *x;
		*x = *y;
		*y = t - (a/b)*(*y);
	}
}
// a*x = 1 (mod n) -> a*x + n*y = 1
ll inv(ll a, ll n) {
	ll x, y, d;
	ex_gcd(a, n, x, y, d);
	return d == 1 ? (x+n)%n : -1;
}

感觉很少用，因为大部分题模的数都是质数，所以可以用费马小定理替代。

费马小定理

若$p$为素数，$a$为正整数，且$a$、$p$互质。 则有$a^{p-1} = 1 \pmod p$

$a∗x≡1\pmod p$

$a*x\equiv a^{p-1}\pmod p$

$x \equiv a^{p-2} \pmod p$

ll fpow(ll x, ll p, ll m) {
	ll rt = 1;
	while (p) {
		if (p&1) rt *= x, rt %= m;
		x *= x; x %= m;
		p >>= 1;
	}
	return rt;
}
fpow(x, p-2, p); // inv(x)

求一个数的逆元，时间复杂度$O(log(p))$

线性求逆元

$p=k*i+r,(1<r<i<p)$

其中 $k = \lfloor \frac{p}{i} \rfloor$，$r = p \mod i$

$k*i+r \equiv 0 \pmod p$

$i^{-1} = -k*r^{-1} \pmod p$

$i^{-1} = -\lfloor \frac{p}{i} \rfloor*(p \mod i)^{-1} \pmod p$

ll inv[N];
inv[1] = 1;
for (int i=2; i<=n; i++) {
		inv[i] = (p-p/i)*inv[p%i]%p;
}