卢卡斯定理

  卢卡斯定理主要是用来求组合数取模，即C(n,m)%p。其适用范围是:组合数很大，但p又不是很大且p是素数的情况(10^6+3也算是“不很大”) 。卢卡斯定理可以表达为:

在写代码时，可以用递归实现:

LL lucas(LL a,LL b,LL p)
{
    return !b?1:lucas(a/p,b/p,p)*comb(a%p,b%p,p)%p;
}

为什么可以转化为lucas(a/p,b/p,p) * comb(a%p,b%p,p)%p这个递归呢？看这里👇

因此，可以利用这样的一个递归实现。 在这里，comb()是求组合数取模的函数(适用于小组合数)，代码为

LL comb(LL n,LL m,LL p)
{
    if(n<m||m<0)
        return 0;
    LL up=1;
    LL down=1;
    for(LL i=n-m+1;i<=n;i++)
        up=(up*i)%p;
    for(LL i=1;i<=m;i++)
        down=(down*i)%p;
    return up*inv(down,p)%p;
}

而inv()是求down的逆元的函数，原理是利用快速幂求a^(p-2)。

中国剩余定理

  中国剩余定理又被称为孙子定理，它来自于一个耳熟能详的数学问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？。转换为数学式子，即为以下这个一元线性同余方程组 那么，要如何求解这个方程组呢？ (我自己至今还是不太懂怎么求解OTZ) 因此，只需要求kM+∑(i=1,n)ai x ti x Mi即可

代码如下：

LL china(int k,LL a[],LL m[])
{
    LL M=1;LL ans=0;
    for(int i=0;i<k;i++)
        M*=m[i];
    for(int i=0;i<k;i++)
    {
        LL tmp=M/m[i];        //tmp==>mi        
        ans=(ans+mulq(tmp*inv(tmp,m[i]),a[i],M))%M;        //ti==>ti*mi=1 (mod mi)
    }
    return (ans+M)%M;            //通解为kM+∑(i=0,k)(ai*ti*Mi) 
}