多次学然后多次不会之后，我决定写一篇东西来记录一下这个方法。
我们要做的是线性递推出([1,p))的所有数的逆元。
[p=ai+b \
ai+bequiv 0mod p \
aiequiv -b \
i^{-1}equiv -ab^{-1}
]
由于(a=lfloor frac{a}{i} floor,b=pmod i)，所以递推式为：
[inv[i]=inv[p\%i]*(p-p/i)
]
多次学然后多次不会之后，我决定写一篇东西来记录一下这个方法。
我们要做的是线性递推出([1,p))的所有数的逆元。
由于(a=lfloor frac{a}{i} floor,b=pmod i)，所以递推式为：