Unknown Treasure

Time Limit: 1500/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 3056    Accepted Submission(s): 1128


Problem Description On the way to the next secret treasure hiding place, the mathematician discovered a cave unknown to the map. The mathematician entered the cave because it is there. Somewhere deep in the cave, she found a treasure chest with a combination lock and some numbers on it. After quite a research, the mathematician found out that the correct combination to the lock would be obtained by calculating how many ways are there to pickm different apples among n of them and modulo it with M.M is the product of several different primes.  
Input On the first line there is an integer T(T≤20) representing the number of test cases.

Each test case starts with three integers n,m,k(1≤m≤n≤1018,1≤k≤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=p1⋅p2⋅⋅⋅pk≤1018 and pi≤105 for every i∈{1,...,k}.  
Output For each test case output the correct combination on a line.  
Sample Input 1 9 5 2 3 5  
Sample Output 6   题意： 问组合数 C(n,m) % M 等于多少
其中 n  m  M 都是 小于等于 10^18 次方的比较大的数字
并且题目给出 M 的唯一分解的所有质因子 p ，求解决上述问题 题解：
首先介绍中国剩余定理：
逆元详解： 本题中求逆元 inv数组 还利用了费马小定理，得到了一个递推性质，然后快速的求了出来
lucas定理：
C（n , m）= C（n%mod , m%mod）* lucas( n/mod , m/mod )
爆longlong的乘法取模处理： LL mul(LL a,LL b,LL mod){///二进制，按位相乘 a=(a%mod+mod)%mod; b=(b%mod+mod)%mod; LL ans=0; while(b){ if(b&1) ans+=a,ans=(ans>=mod?ans-mod:ans); b>>=1; a<<=1; a=(a>=mod?a-mod:a); } return ans; }


#include #include #include using namespace std; #define maxn 100005 #define LL long long LL fac[maxn],inv[maxn]; LL powmod(LL a,LL b,LL mod){ LL ans=1; while(b){ if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } void init(int n){ fac[0]=1; for(int i=1;i=0;i--) inv[i]=inv[i+1]*(i+1)%n; } LL lucas(LL n,LL m,LL mod){ LL ans=1; while(n&&m){ LL a=n%mod,b=m%mod; if(a=mod?ans-mod:ans); b>>=1; a<<=1; a=(a>=mod?a-mod:a); } return ans; } LL china(LL n,LL* a,LL* m){ LL M=1,w,gcd,x,y,ans=0; for(int i=0;i