线性求逆元
求 (i) 在 (pmod P)意义下的逆元。
已知：
[k*i+r=P
]
则在(mod P)意义下为：
[k*i+r equiv 0 pmod P
]
同时乘以 (i^{-1}),(r^{-1})得：
[k*r^{-1}+i^{-1}equiv0pmod P
]
整理得：
[i^{-1}equiv-k*r^{-1}pmod P
]
带入原数据得：
[i^{-1}equiv -leftlfloorfrac{P}{i}
ight
floor*(P \% i)^{-1}
]
即：
[f[i] = (P-P/i)*f[P\%i]
]