求n个逆元的O(n)算法

它的推导过程如下，设，那么

       

对上式两边同时除，进一步得到

       

再把和替换掉，最终得到

       

初始化，这样就可以通过递推法求出模奇素数的所有逆元了。

转自  http://blog.csdn.net/acdreamers/article/details/8220787