Unknown Treasure
Time Limit: 1 Sec
Memory Limit: 256 MB
题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=5446
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 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==)
{
x=,y=;
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 ;
ll ans = qpow(x,y>>,m);
ans = ans*ans%m;
if(y&)ans = ans*x%m;
return ans;
} ll nump(ll x,ll p)
{
ll ans = ;
while(x)ans+=x/p,x/=p;
return ans;
}
ll fac(ll n,ll p,ll pk)
{
if(n==)return ;
ll ans = ;
for(ll i=;i<=pk;i++)
{
if(i%p==)continue;
ans = ans*i%pk;
}
ans = qpow(ans,n/pk,pk);
ll to = n%pk;
for(ll i =;i<=to;i++)
{
if(i%p==)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 = ;
ll x = p;
for(ll i =;i*i<=x&&x>;i++)
{
ll k=,pk=;
while(x%i==)
{
x/=i;
k++;
pk*=i;
}
if(k>)
ans=(ans+cal(n,m,p,i,pk))%p;
}
if(x>)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<) ret+=M;
}
x+=x;
x%=M;
if(x<) x+=M;
}
return ret;
}
void solve(ll r[],ll s[],int t)
{
ll M=1LL,ans=0LL;
ll p[],q[],e[];
for(int i=;i<t;i++)
M*=r[i];
for(int i=;i<t;i++)
{
ll tmp=M/r[i],tt;
extend_gcd(tmp,p[i],r[i],q[i]);
p[i]%=M;
if(p[i]<) p[i]+=M;
e[i]=qtpow(tmp,p[i],M);
tt=qtpow(e[i],s[i],M);
ans=(ans+tt)%M;
if(ans<) ans+=M;
}
printf("%I64d\n",ans);
} ll CCC[],DDD[];
int main()
{
int t;
scanf("%d",&t);
int num = ;
ll n,m,p;
while(t--)
{
memset(CCC,,sizeof(CCC));
memset(DDD,,sizeof(DDD));
scanf("%I64d %I64d %d",&n,&m,&num);
for(int i=;i<num;i++)
{
scanf("%I64d",&CCC[i]);
DDD[i]=mCnmodp(n,m,CCC[i]);
}
solve(CCC,DDD,num);
}
return ;
}