知识点:各种求逆元的技术

乘法逆元定义: 若a∗x≡1(mod p) ，且 a 与 b 互质，那么我们就能定义: x 为 a 的逆元，记为 x = a^(-1)

逆元存在条件: 当a与p互素时，a关于模p的乘法逆元有唯一解。如果不互素，则无解。如果p为素数，则从2到p-1的任意数都与f互素，即在2到p-1之间都恰好有一个关于模p的乘法逆元。

//注:每种方法都有它的局限

乘法逆元的一大应用是模意义下的除法，除法在模意义下并不是封闭的，但我们可以根据上述公式，将其转化为乘法。

$\frac{x}{y} = x*y^{-1}(mod p)$

转换过程:将y在mod p 的意义下的逆元求出来，再与x相乘，再mod p即可.

解法1.费马小定理+快速幂求逆元(p一定要质数)

复杂度: O(loga)

推导:

a^(p-1) = 1(mod p) //应用条件:p是素数且 a不为p的倍数

a*a^(p-2) = 1(mod p)

aˆ(p-2) = a^-1(mod p )

所以某数在模p意义下的逆元为 a^(p-2)%p

本质：求解线性同余方程ax = c (mod p)当c=1的情况

注意：(p不用为质数但a,p要互质，不然a^(-1)无解)

复杂度: O(logmax(a,b)

推导:

ax = 1(mod p) => ax -py = 1(此处可以看出a,p要互质)

Exgcd(a,p,x,y)

注:求出来的值可能为负数：经过以下操作可将变换成最小正整数解: x = (x % p + p) % p;(这个步骤能够将x调整到模p意义下的逆元)

复杂度:O(n)

注意点:1.当a>p时，a对p取模即可求

[if !supportLists]2. [endif]当p不为素数时,不是每个数都有逆元

推导:

开始:p%i = p–[p/i]*i (众所周知….)

移项:p%i + [p/i]*i = p令a=p%i,b=[p/i],

又得: a + b*i = p

所以a+ b*i= 0 (mod p)

继续移项: i^-1 = -b/a = -[p/i] * (p%i)^-1

又因为p%i < i且边界条件:1*1^-1=1 即 inv[1] = 1

所以inv[p%i]必定在inv[i]之前就得出来了

所以递推式: inv[i] = (p-p/i) %p *inv[p%i]%p

注;为什么是p-p/i:因为我们求得是mod p 意义下的逆元,所以这个要将负数-p/i调整到0~p-1

$设第x项阶乘为x!,其逆元为x!^-1,那么有递推式:(x-1)^{-1} = (x!)^{-1}*x$

所以从后往前递推求.