Unknown Treasure

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

题意：M=p1*p2*...pk；求C（n，m）%M，pi小于10^5，n,m,M都是小于10^18。 pi为质数

题解：首先M=x*pi(1<=i<=k)

M不一定是质数所以只能用Lucas定理求k次 C（n，m）%Pi得到 B[i];

最后会得到一个同余方程组
x≡B[0](mod p[0])
x≡B[1](mod p[1])
x≡B[2](mod p[2])
......
解这个同余方程组用中国剩余定理

但ll*ll都会爆所以用快速乘

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<string>

#include<iostream>

#include<queue>

#include<cmath>

#include<map>

#include<stack>

#include<set>

using namespace std;

#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )

#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )

#define CLEAR( a , x ) memset ( a , x , sizeof a )

const int INF=0x3f3f3f3f;

typedef long long LL;

LL M[],B[];

int t;

LL n,m,p,num;

LL exgcd(LL a, LL b, LL &x, LL &y)

{

    if (!b)

    {

        x = ;

        y = ;

        return a;

    }

    LL gcd = exgcd(b, a % b, x, y);

    LL t = x;

    x = y;

    y = t - (a / b) * x;

    return gcd;

}

LL mult(LL a,LL b,LL p)

{

    LL ans=;

    while(b)

    {

        if(b&)

            ans=(ans+a)%p;

        b>>=;

        a=(a+a)%p;

    }

    return ans;

}

LL inverse(LL num, LL mod)

{

    LL x, y;

    exgcd(num, mod, x, y);

    return (x % mod + mod) % mod;

}

LL C(LL a, LL b, LL mod)

{

    if (b > a)

        return ;

    LL t1 = , t2 = ;

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

    {

        t2 *= i;

        t2 %= mod;

        t1 *= (a - i + );

        t1 %= mod;

    }

    return mult(t1,inverse(t2, mod),mod);

}

LL lucas(LL n, LL m, LL p)

{

    if (m == )

        return ;

    return mult(C(n % p, m % p, p),lucas(n / p, m / p, p),p);

}

LL China(LL m[],LL b[],int k)//m:模数 b:余数

{

    LL n=,xx,yy;

    LL ans=;

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

        n*=M[i];

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

    {

        LL t=n/M[i];

        exgcd(t,M[i],xx,yy);

        LL x1=mult(xx,t,n);

        LL x2=mult(x1,b[i],n);

        ans=(ans+x2)%n;

    }

    return (ans%n+n)%n;

}

int main()

{

    scanf("%d",&t);

    while(t--)

    {

        scanf("%lld%lld%lld",&n,&m,&num);

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

        {

            scanf("%d",&p);

            M[i]=p;

            B[i]=lucas(n,m,p);

        }

        LL ans=China(M,B,num);

        printf("%lld\n",ans);

    }

    return ;

}

来自Tisuama

巴特西

HDU 5446 CRT+Lucas+快速乘

Unknown Treasure

最新文章

热门文章