HDU-5466 Unknown Treasure

题目描述

给出$n$和$m$以及$k$个质数，设$M$为$\prod^{k}_{i=1}p_i $，$p_i$互不相同，求$C(n,m)%M$

Input

第一行一个$T$表示数据组数。

对于每组数据第一行$n$,$m$,$k$。

第二行$k$个质数，其互不相同。

$1≤m≤n≤10^{18}$

$1≤k≤10$

$p_i≤10^5$

Output

对于每组数据输出答案。

Sample Input

1
9 5 2
3 5

Sample Output

扩展卢卡斯定理即可。

首先，对于一个模数为质数的的组合数，我们可以直接利用卢卡斯定理。

$C(n,m)\%p=C(n/p,m/p)*C(n\%p,m\%p)\%p$。

可是题目中给出是一个合数，不是质数，那咋办呀？

我们发现模数最多由不超过$10$个不同的质数组成，对于一个$C(n,m)$，我们可以直接求出对于每个质数的取模结果，设第$i$个结果为$res_i$。

则我们就有一个方程组
\[\begin{cases}C(n,m)=res_1\%p_1 \\C(n,m)=res_2\%p_2 \\...... \\C(n,m)=res_k\%p_k\end{cases}\]
我们直接利用中国剩余定理合并即可。

#include <cstdio>
#include <iostream>

using namespace std;

#define int long long
#define reg register
#define clr(a,b) memset(a,b,sizeof a)
#define Mod(x) (x>=mod)&&(x-=mod)
#define abs(a) ((a)<0?-(a):(a))
#define debug(x) cerr<<#x<<"="<<x<<endl;
#define debug2(x,y) cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl;
#define debug3(x,y,z) cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl;
#define rep(a,b,c) for(reg int a=(b),a##_end_=(c); a<=a##_end_; ++a)
#define ret(a,b,c) for(reg int a=(b),a##_end_=(c); a<a##_end_; ++a)
#define drep(a,b,c) for(reg int a=(b),a##_end_=(c); a>=a##_end_; --a)
#define erep(i,G,x) for(int i=(G).Head[x]; i; i=(G).Nxt[i])
#pragma GCC optimize(2)

inline int Read(void) {
    int res=0,f=1;
    char c;
    while(c=getchar(),c<48||c>57)if(c=='-')f=0;
    do res=(res<<3)+(res<<1)+(c^48);
    while(c=getchar(),c>=48&&c<=57);
    return f?res:-res;
}

template<class T>inline bool Min(T &a, T const&b) {
    return a>b?a=b,1:0;
}
template<class T>inline bool Max(T &a, T const&b) {
    return a<b?a=b,1:0;
}
const int N=25,M=1e5+5;

int n,m,k,res[N],mod[N],a[N],pos[N];

int Exgcd(int a, int b, int &x, int &y) {
    if(!b) {
        x=1,y=0;
        return a;
    }
    int g=Exgcd(b,a%b,y,x);
    y-=a/b*x;
    return g;
}

inline int Excrt(void) {
    int M=mod[1],ans=res[1],x,y;
    rep(i,2,k) {
        int g=Exgcd(M,mod[i],x,y);
        if((res[i]-ans)%g)return -1;
        x*=(res[i]-ans)/g,y=mod[i]/g,x=(x%y+y)%y;
        ans=M*x+ans,M=M/g*mod[i],ans%=M;
    }
    int z=(ans%M+M)%M;
    return z;
}

int Mod;

int Pow(int x,int y) {
    int res=1;
    while(y) {
        if(y&1)res=(res*x)%Mod;
        x=(x*x)%Mod,y>>=1;
    }
    return res;
}

inline int C(int x,int y) {
    if(y>x)return 0;
    int up=1,down=1;
    rep(i,x-y+1,x)up=up*i%Mod;
    rep(i,1,y)down=down*i%Mod;
    return up*Pow(down,Mod-2)%Mod;
}

int Lucas(int x,int y) {
    if(!y)return 1;
    return Lucas(x/Mod,y/Mod)*C(x%Mod,y%Mod)%Mod;
}

inline void _main(void) {
    int T=Read(),Case=0;
    while(T--) {
        n=Read(),m=Read(),k=Read();
        rep(i,1,k) Mod=mod[i]=Read(),res[i]=Lucas(n,m);
        printf("%lld\n",Excrt());
    }
}

signed main() {
    _main();
    return 0;
}