C++乘法逆元

当一个题目让你求方案数时常要取余，虽然
(a+b)%p=(a%p+b%p)%p
(a?b)%p=(a%p?b%p)%p
(a×b)%p=(a%p×b%p)%p
但是
(ab)%p≠(a%pb%p)%p
由于会出现这种情况，所以就要逆元了
一般情况下，当ax=1时，x 是 a 的倒数，x=1a
毕竟是取余，所以当ax≡1(modp)时， x 叫做 a 关于 p 的逆元，用 a?1 表示
于是 (ab)%p=(a%p×b?1%p)%p
这样就把除法转换成乘法，解决了问题