【数论】逆元

新生赛傻逼突然忘了怎么求逆元……还花一个小时企图手推。

求单个数的素数逆元：费马小定理就可以了。a^(p-1)≡1。所以a的逆元就是a^(p-2).

求【1，n】的逆元：

　　rep(i,2,maxn-1) 　inv[i]=mm-(mm/i)*inv[mm%i]%mm; 

http://blog.miskcoo.com/2014/09/linear-find-all-invert