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

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

2024-08-24 08:07:21   221人阅读

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(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
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 卢卡斯+中国剩余定理


联系
我们