首页 > 代码库 > hdu 5446 Unknown Treasure 卢卡斯+中国剩余定理

hdu 5446 Unknown Treasure 卢卡斯+中国剩余定理

Unknown Treasure

Time Limit: 1500/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)


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 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(T20) representing the number of test cases.

Each test case starts with three integers n,m,k(1mn1018,1k10) 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=p1p2pk1018 and pi105 for every i{1,...,k}.
 

 

Output
For each test case output the correct combination on a line.
 

 

Sample Input
19 5 23 5
 

 

Sample Output
6
 

 

Source
2015 ACM/ICPC Asia Regional Changchun Online
题意:求c(n,m)%(p1*p2*...*pk);
思路:求出每个c(n,m)%p1=a1......求出a数组;
   然后根据a求中国剩余即是答案;
#include<bits/stdc++.h>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14const int N=1e5+10,M=1e6+10,inf=1e9+10;const ll INF=1e18+10,mod=2147493647;ll p[20],a[20];ll n,m;ll mulmod(ll x,ll y,ll m){    ll ans=0;    while(y)    {        if(y%2)        {            ans+=x;            ans%=m;        }        x+=x;        x%=m;        y/=2;    }    ans=(ans+m)%m;    return ans;}ll ff(ll x,ll p){    ll ans=1;    for(int i=1;i<=x;i++)        ans*=i,ans%=p;    return ans;}ll pow_mod(ll a, ll x, ll p)   {    ll ret = 1;    while (x)   {        if (x & 1)  ret = ret * a % p;        a = a * a % p;        x >>= 1;    }    return ret;}ll Lucas(ll n, ll k, ll p) {       //C (n, k) % p     ll ret = 1;     while (n && k) {        ll nn = n % p, kk = k % p;        if (nn < kk) return 0;                   //inv (f[kk]) = f[kk] ^ (p - 2) % p        ret = ret * ff(nn,p) * pow_mod (ff(kk,p) * ff(nn-kk,p) % p, p - 2, p) % p;        n /= p, k /= p;     }     return ret;}void exgcd(ll a, ll b, ll &x, ll &y){    if(b == 0)    {        x = 1;        y = 0;        return;    }    exgcd(b, a % b, x, y);    ll tmp = x;    x = y;    y = tmp - (a / b) * y;}ll CRT(ll a[],ll m[],ll n){    ll M = 1;    ll ans = 0;    for(ll i=1; i<=n; i++)        M *= m[i];    for(ll i=1; i<=n; i++)    {        ll x, y;        ll Mi = M / m[i];        exgcd(Mi, m[i], x, y);        //ans = (ans + Mi * x * a[i]) % M;        ans = (ans +mulmod( mulmod( x , Mi ,M ), a[i] , M ) ) % M;    }    ans=(ans + M )% M;    return ans;}int main(){    int T;    scanf("%d",&T);    while(T--)    {        int k;        scanf("%lld%lld%d",&n,&m,&k);        for(int i=1;i<=k;i++)            scanf("%lld",&p[i]);        for(int i=1;i<=k;i++)            a[i]=Lucas(n,m,p[i]);        printf("%lld\n",CRT(a,p,k));    }    return 0;}

 

hdu 5446 Unknown Treasure 卢卡斯+中国剩余定理