Unknown Treasure
Time Limit: 1 Sec
Memory Limit: 256 MB
题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=5446Description
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 pick m 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
HINT
题意
给你n,m,num
然后给你num个数，k1,k2....,knum
然后让你求C(n,m)%(k1*k2*....*knum)
题解：
首先，C(n,m)%k我们是会求的，大概这部分子问题是一个很经典的题目。
假设你会求了，那么我们就可以由此得到num个答案，是%k1,k2,k3....knum后得到的值
然后我们就可以看出就是类似韩信点兵一样的题，三个人一组剩了2个，五个人一组剩了2个这种……
这时候，就用中国剩余定理处理处理就好了
注意ll*ll会爆，所以得手写个快速乘法
代码：
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //************************************************************************************** void extend_gcd(ll a,ll &x,ll b,ll &y) { if(b==0) { x=1,y=0; return; } ll x1,y1; extend_gcd(b,x1,a%b,y1); x=y1; y=x1-(a/b)*y1; } ll inv(ll a,ll m) { ll t1,t2; extend_gcd(a,t1,m,t2); return (t1%m+m)%m; } ll qpow(ll x,ll y,ll m) { if(!y)return 1; ll ans = qpow(x,y>>1,m); ans = ans*ans%m; if(y&1)ans = ans*x%m; return ans; } ll nump(ll x,ll p) { ll ans = 0; while(x)ans+=x/p,x/=p; return ans; } ll fac(ll n,ll p,ll pk) { if(n==0)return 1; ll ans = 1; for(ll i=1;i<=pk;i++) { if(i%p==0)continue; ans = ans*i%pk; } ans = qpow(ans,n/pk,pk); ll to = n%pk; for(ll i =1;i<=to;i++) { if(i%p==0)continue; ans = ans*i%pk; } return fac(n/p,p,pk)*ans%pk; } ll cal(ll n,ll m,ll p ,ll pi,ll pk) { ll a = fac(n,pi,pk),b=fac(m,pi,pk),c=fac(n-m,pi,pk); ll d = nump(n,pi)-nump(m,pi)-nump(n-m,pi); ll ans = a%pk * inv(b,pk)%pk * inv(c,pk)%pk*qpow(pi,d,pk)%pk; return ans*(p/pk)%p*inv(p/pk,pk)%p; } ll mCnmodp(ll n,ll m,ll p) { ll ans = 0; ll x = p; for(ll i =2;i*i<=x&&x>1;i++) { ll k=0,pk=1; while(x%i==0) { x/=i; k++; pk*=i; } if(k>0) ans=(ans+cal(n,m,p,i,pk))%p; } if(x>1)ans=(ans+cal(n,m,p,x,x))%p; return ans; } ll qtpow(ll x,ll y,ll M) { ll ret=0LL; for(x%=M;y;y>>=1LL) { if(y&1LL) { ret+=x; ret%=M; if(ret<0) ret+=M; } x+=x; x%=M; if(x<0) x+=M; } return ret; } void solve(ll r[],ll s[],int t) { ll M=1LL,ans=0LL; ll p[20],q[20],e[20]; for(int i=0;i<t;i++) M*=r[i]; for(int i=0;i<t;i++) { ll tmp=M/r[i],tt; extend_gcd(tmp,p[i],r[i],q[i]); p[i]%=M; if(p[i]<0) p[i]+=M; e[i]=qtpow(tmp,p[i],M); tt=qtpow(e[i],s[i],M); ans=(ans+tt)%M; if(ans<0) ans+=M; } printf("%I64d ",ans); } ll CCC[20],DDD[20]; int main() { int t; scanf("%d",&t); int num = 0; ll n,m,p; while(t--) { memset(CCC,0,sizeof(CCC)); memset(DDD,0,sizeof(DDD)); scanf("%I64d %I64d %d",&n,&m,&num); for(int i=0;i<num;i++) { scanf("%I64d",&CCC[i]); DDD[i]=mCnmodp(n,m,CCC[i]); } solve(CCC,DDD,num); } return 0; }