出现的问题 计算组合数（公式如下）时， $$ C_{n}^{m}=\frac{n!}{m!\times(n-m)!} $$ 如果n很大，一般会要求将结果对某个数（比如 $1e9$ ）取模，显然 $n!$ 会非常大，可能 long long 都存不下，所以要一边乘，一边取模。数论中有三个式子 $$ (a + b) % p = (a % p + b % p)%p $$ $$ (a - b) % p = (a % p - b % p) % p $$ $$ (a * b) % p = ((a % p) \times (b % p)) % p $$ 但是对于除法却不成立，所以需要用逆元来解决 简介 若$a \times x % M = 1$，我们就称$x$是$a$的逆元，$x$可以写作$a^{-1}$次方（相当于整除中的倒数) 用途 假设我们需要求$a \div b % M$的值，而由于上述种种原因，我们不能直接除，这时就可以对式子进行一些操作: $$ a \div b % M = a \div b \times 1 % M = a \div b \times (b \times b^{-1})...