ACM-ICPC 2015 Changchun Preliminary Contest J. Unknown Treasure （卢卡斯定理+中国剩余定理）

题目链接：https://nanti.jisuanke.com/t/A1842

题目大意：给定整数n,m,k,其中1≤m≤n≤10¹⁸,k≤10,

然后给出k个素数，保证M=p[1]*p[2]……*p[k]≤10¹⁸,p[i]≤10⁵

求C(n,m)%(p[1]*p[2]……*p[k])

解题思路：因为模数太大，所以我们先用卢卡斯定理求出对每个素数的模，然后再通过中国剩余定理就可以求得对它们的乘积的模。

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll M,n,m,k,a[],b[];

ll qmul(ll a,ll b,ll p){

    ll res=;

    while(b){

        if(b&) res=(res+a)%p;

        b>>=;

        a=(a+a)%p;

    }

    return res;

}

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

    if(!b){

        x=,y=,d=a;

    }else{

        exgcd(b,a%b,y,x,d);

        y-=a/b*x;

    }

}

ll INV(ll a,ll p){

    ll x,y,d;

    exgcd(a,p,x,y,d);

    return (x%p+p)%p;

}

ll C(ll a,ll b,ll p){

    if(a<b)return ;

    if(b==)return ;

    if(a-b<b)b=a-b;

    ll ca=,cb=;

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

        ca=ca*(a-i)%p;

        cb=cb*(b-i)%p;

    }

    return ca*INV(cb,p)%p;

}

ll lucas(ll a,ll b,ll p){

    ll res=;

    while(a&&b){

        res=res*C(a%p,b%p,p)%p; //C(n,m)%p=C(n%p,m%p)*C(n/p,m/p)%p

        a/=p;

        b/=p;

    }

    return res;

}

ll crt(){

    ll x,y,d,res=;

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

        ll Mi=M/b[i];

        exgcd(Mi,b[i],x,y,d);

        x=(x%b[i]+b[i])%b[i];

        ll tmp=qmul(a[i],qmul(Mi,x,M),M);

        res=(res+tmp)%M;

    }

    return (res%M+M)%M;

}

int main(){

    int t;

    scanf("%d",&t);

    while(t--){

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

        M=;

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

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

            a[i]=lucas(n,m,b[i]);

            M*=b[i];

        }

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

    }

    return ;

}

巴特西

ACM-ICPC 2015 Changchun Preliminary Contest J. Unknown Treasure （卢卡斯定理+中国剩余定理）

最新文章

热门文章