定义：对于正整数a和m，如果有 ax=1(mod m),那么把这个同余方程中x的最小正整
数解叫做a模m的逆元。
求法：1.扩展欧几里得
2.根据费马小定理得到逆元为a^(m-2) mod m。
证明：当m是素数时，由费马小定理
a^(p-1)=1(mod m)
=> a^(p-2)*a=1(mod m)
=> a^(p-2)=a^-1(mod m)
所以：a^(p-2)mod m 是a在mod m下的逆元。
问题：ans=(a/b)mod m
当a与m互素时，可以用exgcd或费马小定理（m是素数），实际上还有一种一
般求解方法：ans = (a/b)mod m = amod(mb)/b
证明：a/b=km+x
a=kbm+bx
amod(bm)=bx
amod(bm)/b=x
(a/b)mod m = amod(bm)/b
有些问题需要求解1->p模p的所有逆元，这里p为奇质数。那么如果用快速幂求时
间复杂度为O(p*logp),如果对于一个1000000级别的素数，这样做的时间复杂度是很
高了。实际上有O(p)的算法，有一个递推式如下:
inv[i]=(M-M/i)*inv[M%i]%M
证明：设t=M/i,k=M%i，那么
=> t*i+k=0(mod M)
=> -t*i=k(mod M)
对上式两边同时除，进一步得到
-t*inv[k]=inv[i](mod M)
再把和替换掉，最终得到
inv[i]=(M-M/i)*inv[M%i]%M
初始化inv[i]=1，这样就可以通过递推求出1->p模奇素数p的所有逆元了。
另外1->p模p的所有逆元值对应中1->p所有的数，比如p=7，那么1->6对应
的逆元是1 4 5 2 3 6。
两个例题：poj1845，bzoj2186
原文：http://www.cnblogs.com/harden/p/6262978.html