问题:求a/b对p的余数
简单，我会(a%p)/(b%p)
很遗憾，除法不满足模运算的分配律，不信你自己去试一试。
那么就需要用到逆元了((i的逆元记作inv[i]))。
若(a*xequiv1 pmod {p}，且a与p互质，那么我们就能定义: x 为 a 的逆元，记为a^{-1})
(那么求frac{a}{b}pmod{p}也就是求 a*inv[b]pmod{p})
Ⅰ.费马小定理求逆元
注意，这种方法只适用于模数p为质数的时候。
(这个定理是说a^{p-1} equiv 1 pmod{p})
(Rrightarrow a^{p-2}equiv a^{-1} pmod{p})
(即a^{p-2}是a在模数p下的逆元)
Ⅱ.(问题:求1至p的所有数对p下的逆元。)
(这个时候即使是ecgcd的O(p logp)也不让人满意，好在我们有个O(p)的线性递推算法)
首先我们知道(1^{-1}=1(mod p),放进递推数组inv[1]=1)
现在假设(k=p/i, r=p\%i)
(Rrightarrow p=k*i+r)
(Rrightarrow k*i+requiv 0 pmod{p})
(Rrightarrow 左右乘上i^{-1}、r^{-1}得k*r^{-1}+i^{-1}equiv0 pmod{p})
(Rrightarrow 移项得i^{-1}equiv -k*r^{-1} pmod{p})
(也就是inv [i] = -(p/i) *inv [p\%i] (mod p))
然后因为我们想得到正数下的逆元，所以稍微变化一下得到
(inv [i]=(p-p/i)* inv [ p\%i ] \%p)
就这么轻松的证完了!!!