Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 721 Accepted Submission(s): 251
On the first line there is an integer $T(T\leq 20)$ representing the number of test cases.
Each test case starts with three integers $n,m,k(1\leq m\leq n\leq 10^{18},1\leq k\leq 10)$ on a line where k is the number of primes. Following on the next line are k different primes p1,...,pk. It is guaranteed that $M=p_1⋅p_2\cdots p_k\leq 10^{18}\, and\, p_i\leq 10^5 for\, every\, i\in\{1,\dots,k\}.$
解题：中国剩余定理+Lucas定理
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int maxn = 101010; 5 LL F[maxn] = {1},a[maxn],m[maxn],N,M,n; 6 void init(LL mod){ 7 for(int i = 1; i < maxn; ++i) 8 F[i] = F[i-1]*i%mod; 9 } 10 LL quickPow(LL base,LL index,LL mod){ 11 LL ret = 1; 12 base %= mod; 13 while(index){ 14 if(index&1) ret = ret*base%mod; 15 index >>= 1; 16 base = base*base%mod; 17 } 18 return ret; 19 } 20 LL Inv2(LL b,LL mod){ 21 return quickPow(b,mod-2,mod); 22 } 23 LL Lucas(LL n,LL m,LL mod){ 24 LL ret = 1; 25 while(n && m){ 26 LL a = n%mod; 27 LL b = m%mod; 28 if(a < b) return 0; 29 ret = ret*F[a]%mod*Inv2(F[b]*F[a-b]%mod,mod)%mod; 30 n /= mod; 31 m /= mod; 32 } 33 return ret; 34 } 35 LL mul(LL a,LL b,LL mod){ 36 if(!a) return 0; 37 return ((a&1)*b%mod + (mul(a>>1,b,mod)<<1)%mod)%mod; 38 } 39 LL CRT(LL a[],LL m[],LL n){ 40 LL M = 1,ret = 0; 41 for(int i = 0; i < n; ++i) M *= m[i]; 42 for(int i = 0; i < n; ++i){ 43 LL x,y,tm = M/m[i]; 44 x = Inv2(tm,m[i]); 45 ret = (ret + mul(mul(tm,x,M),a[i],M))%M; 46 } 47 return ret; 48 } 49 int main(){ 50 int kase; 51 scanf("%d",&kase); 52 while(kase--){ 53 scanf("%I64d%I64d%I64d",&N,&M,&n); 54 for(int i = 0; i < n; ++i){ 55 scanf("%I64d",m + i); 56 init(m[i]); 57 a[i] = Lucas(N,M,m[i]); 58 } 59 printf("%I64d\n",CRT(a,m,n)); 60 } 61 return 0; 62 }
原文：http://www.cnblogs.com/crackpotisback/p/4808156.html
