HDU 3037 aving Beans [LUCAS定理]

　　求C(n+m,m)%p ,n和m很大,p是小于10^5的素数。

　　LUCAS定理。

 1 #include <string.h>
 2 #include <stdio.h>
 3 typedef long long LL;
 4 int cas;
 5 LL n, m, p;
 6 LL fac[100005];
 7 LL powmod(LL a, LL b, LL p){
 8     LL ans = 1, tmp = a;
 9     for (; b; b >>= 1, tmp = tmp * tmp % p)
10         if (b&1) ans = ans * tmp % p;
11     return ans;
12 }
13 LL lucas(LL n, LL m, LL p){
14     LL ans = 1;
15     while (n&&m) {
16         LL a = n%p, b = m%p;
17         if (a < b) return 0;
18         ans = ans * fac[a] * powmod(fac[b]*fac[a-b]%p,p-2,p) % p;
19         n /= p, m /= p;
20     }
21     return ans;
22 }
23 void getfact(LL p){
24     fac[0]=1;
25     for (int i = 1; i <= p; i++)
26         fac[i] = fac[i-1] * i % p;
27 
28 }
29 int main(){
30     scanf("%d", &cas);
31     while (cas--) {
32         scanf("%I64d%I64d%I64d", &n, &m, &p);
33         getfact(p);
34         printf("%I64d\n", lucas(n+m, m, p));
35     }
36     return 0;
37 }