题目大意

输入n,m,k以及k个质数p1,p2,...,pk，求$C_n^m\%(p1*p2*...*pk)$。

思路

听群里大佬说了一句扩展Lucas，然后就去学（其实也可以中国剩余定理+Lucas）。

这里主要想说一下这题的数据，极容易爆long long。所以，

1.乘之前一定要%！

2.mod可能是1e18范围的，就要用快速乘！

代码

1 #include
     
        2   3 using namespace std;  4   5 long long n,m,k,geshu[100005],prim[15],cn,M;  6 long long T;  7   8 long long qa(long long a,long long b,long long p)  9 { 10     long long ret=0; 11     while(b) 12     { 13         if(b&1) 14         { 15             ret+=a; 16             ret%=p; 17         } 18         a<<=1; 19         a%=p; 20         b>>=1; 21     } 22     return ret; 23 } 24  25 long long pw(long long a,long long b,long long p) 26 { 27     long long ret=1; 28     while(b) 29     { 30         if(b&1) 31         { 32             ret*=a;ret%=p; 33         } 34         a*=a;a%=p;b>>=1; 35     } 36     return ret%p; 37 } 38  39 long long exgcd(long long a,long long b,long long &x,long long &y) 40 { 41     if(b==0) 42     { 43         x=1;y=0; 44         return a; 45     } 46     long long xx,yy,ret=exgcd(b,a%b,xx,yy); 47     x=yy; 48     y=xx-a/b*yy; 49     return ret; 50 } 51  52 long long fac(long long n,long long p,long long pk) 53 { 54     if(n==0)return 1; 55     long long ret=1; 56     for(long long i=1;i