求一个数a的模p（一般为质数，否则有些数求不出逆元）的逆元。 (1)

费马小定理：

费马小定理是数论中的一个重要定理，其内容为： 假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p）。即：假如a是整数，p是质数，且a,p互质，那么a的(p-1)次方除以p的余数恒等于1。 则a的逆元是（a%p）^(p - 1)，要求p为质数，且（a，p）= 1，a为整数。注意：a>p时先取模。 欧拉定理:在数论中，欧拉定理,（也称费马-欧拉定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a互质，则:  则a的逆元是a^(p - 1),要求a和p互质，且a和p为正整数。

（2）


求组合数方法 （1）递推 （2）利用逆元和公式（一般要求mod p为质数） 。
cm(a,b) = (a!/(a-b)!) / (b!) mod p  = a! * inv(b!) * inv( (a - b)! ) mod p = a! * (b!*(a-b)!)^(p-2) mod p （3）利用Lucas定理（一般要求mod p为质数）。http://blog.csdn.net/wukonwukon/article/details/7341270 数论Lucas定理是用来求 c(n,m) mod p的值,p是素数（从n取m组合，模上p）。 描述为: Lucas(n,m,p)=cm(n%p,m%p)* Lucas(n/p,m/p,p) Lucas(x,0,p)=1; 而 cm(a,b)=a! * (b!*(a-b)!)^(p-2) mod p 也= (a!/(a-b)!) * (b!)^(p-2)) mod p 这里，其实就是直接求 (a!/(a-b)!) / (b!) mod p 由于 (a/b) mod p = a * b^(p-2) mod p 注：对于大组合数取模，n,m不大于10^5的话，用逆元的方法，可以解决。对于n,m大于10^5的话，那么要求p<10^5，这样就是Lucas定理了，将n,m转化到10^5以内解。
http://www.kuangbin.net/archives/lucas_theorem#more-228
http://blog.csdn.net/acm_cxlove/article/details/7844973
Lucas定理求组合数的模板：  模板题:hdu3037 Saving Beans #define LL long long LL PowMod(LL a,LL b,LL MOD){ LL ret=1; while(b){ if(b&1) ret=(ret*a)%MOD; a=(a*a)%MOD; b>>=1; } return ret; } LL fac[100005]; LL Get_Fact(LL p){ fac[0]=1; for(int i=1;i<=p;i++) fac[i]=(fac[i-1]*i)%p; } LL Lucas(LL n,LL m,LL p){ LL ret=1; while(n&&m){ LL a=n%p,b=m%p; if(a
LL F[100010]; void Get_F(LL p) { F[0] = 1; for(int i = 1;i <= p;i++) F[i] = F[i-1]*i%p; } //LL inv(LL a,LL m) //{ // if(a == 1)return 1; // return inv(m%a,m)*(m-m/a)%m; //} LL inv(LL x, LL M) { LL r, y; for (r = 1, y = M - 2; y; x = x * x % M, y >>= 1) (y & 1) && (r = r * x % M); return r; } LL Lucas(LL n,LL m,LL p) { LL ans = 1; while(n&&m) { LL a = n%p; LL b = m%p; if(a < b)return 0; ans = ans*F[a]%p*inv(F[b]*F[a-b]%p,p)%p; n /= p; m /= p; } return ans; }