首页 > 代码库 > hdu 5446 Unknown Treasure (Lucas定理+中国剩余定理+快速乘)

hdu 5446 Unknown Treasure (Lucas定理+中国剩余定理+快速乘)

2024-10-05 09:48:02   219人阅读

题意：c( n, m)%M    M = P1 * P2 * ......* Pk （其中Pk是素数)

思路：Lucas定理中C(n,m)%M，M必须是素数，当M不是素数时，我们可以把它拆成素数的乘积

如果x=C(n,m)%M ,M=p1*p2*..*pk;  a[i]=Lucas(n,m)%pi；

xΞa[1](mod p1)

xΞa[2](mod p2)

...

xΞa[k](mod pk)

用中国剩余定理就可以把x求出来

注意到这道题ll*ll

由于计算机底层设计的原因，做加法往往比乘法快的多，因此将乘法转换为加法计算将会大大提高（大数，比较小的数也没必要）乘法运算的速度，除此之外，当我们计算a*b%mod的时候，往往较大的数计算a＊b会超出long long int的范围，这个时候使用快速乘法方法也能解决上述问题．

ps:用中国剩余定理+快速乘时

 ll tmp=qmult(x,Mi,M);只能写成 x*Mi 而 Mi*x 还有写成下面的样子都会错...
 tmp=qmult(tmp,a[i],M);
 //ll tmp=qmult(a[i],Mi,M);
 //tmp=qmult(tmp,x,M);

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long

using namespace std;

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    ll gcd=exgcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-a/b*y;
    return gcd;
}

ll qmult(ll a,ll b,ll mod)
{
    ll ans=0;
    while(b)
    {
        if(b&1)
        {
            ans=(ans+a)%mod;
        }
        b=b/2;
        a=(a+a)%mod;
    }
    return ans;
}

ll inv(ll num,ll mod)
{
    ll x,y;
    exgcd(num,mod,x,y);
    return (x%mod+mod)%mod;
}

ll com(ll n,ll m,ll mod)
{
    if(n<m) return 0;
    else if(n==m) return 1;
    ll t1=1;
    ll t2=1;
    for(ll i=1;i<=m;i++)
    {
        t1=((t1%mod)*(i%mod))%mod;
        t2=((t2%mod)*((n-i+1)%mod))%mod;
    }
    return qmult(t2,inv(t1,mod),mod);
}

ll Lucas(ll n,ll m,ll mod)
{
    if(m==0) return 1;
    else return qmult(com(n%mod,m%mod,mod),Lucas(n/mod,m/mod,mod),mod);
}

ll CRT(ll a[],ll m[],ll n)
{
    ll M=1;
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        M=M*m[i];
    }
    for(int i=0;i<n;i++)
    {
        ll Mi;
        Mi=M/m[i];
        ll x,y;
        exgcd(Mi,m[i],x,y);
        ll tmp=qmult(x,Mi,M);
        tmp=qmult(tmp,a[i],M);
        //ll tmp=qmult(a[i],Mi,M);
        //tmp=qmult(tmp,x,M);
        ans=(ans+tmp)%M;
    }
    return (ans%M+M)%M;
}

int main(int argc, char const *argv[])
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll n,m,k;
        scanf("%lld %lld %lld",&n,&m,&k);
        ll a[15],b[15];
        for(int i=0;i<k;i++)
        {
            scanf("%lld",&b[i]);
            a[i]=Lucas(n,m,b[i]);
        }
        ll ans=CRT(a,b,k);
        printf("%lld\n",ans  );
    }
    return 0;
}

 

hdu 5446 Unknown Treasure (Lucas定理+中国剩余定理+快速乘)


联系
我们