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

1
9 5 2
3 5

Sample Output

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-14

const int N=1e5+,M=1e6+,inf=1e9+;

const ll INF=1e18+,mod=;

ll p[],a[];

ll n,m;

ll mulmod(ll x,ll y,ll m)

{

    ll ans=;

    while(y)

    {

        if(y%)

        {

            ans+=x;

            ans%=m;

        }

        x+=x;

        x%=m;

        y/=;

    }

    ans=(ans+m)%m;

    return ans;

}

ll ff(ll x,ll p)

{

    ll ans=;

    for(int i=;i<=x;i++)

        ans*=i,ans%=p;

    return ans;

}

ll pow_mod(ll a, ll x, ll p)   {

    ll ret = ;

    while (x)   {

        if (x & )  ret = ret * a % p;

        a = a * a % p;

        x >>= ;

    }

    return ret;

}

ll Lucas(ll n, ll k, ll p) {       //C (n, k) % p

     ll ret = ;

     while (n && k) {

        ll nn = n % p, kk = k % p;

        if (nn < kk) return ;                   //inv (f[kk]) = f[kk] ^ (p - 2) % p

        ret = ret * ff(nn,p) * pow_mod (ff(kk,p) * ff(nn-kk,p) % p, p - , p) % p;

        n /= p, k /= p;

     }

     return ret;

}

void exgcd(ll a, ll b, ll &x, ll &y)

{

    if(b == )

    {

        x = ;

        y = ;

        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 = ;

    ll ans = ;

    for(ll i=; i<=n; i++)

        M *= m[i];

    for(ll i=; 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=;i<=k;i++)

            scanf("%lld",&p[i]);

        for(int i=;i<=k;i++)

            a[i]=Lucas(n,m,p[i]);

        printf("%lld\n",CRT(a,p,k));

    }

    return ;

}

巴特西

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

Unknown Treasure

最新文章

热门文章