$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

Lucas定理： $C_a^b\equiv{C_{a \bmod p}^{b \bmod p}\cdot C_{a/p}^{b/p}}\pmod{p}$

证明：

$\because \ C_p^n\equiv0\pmod{p}$，其中 $0<n<p$

$\therefore \ (a+b)^p = \sum\limits_{n=0}^pC_p^n a^n b^{p-n} \equiv{a^p+b^p}\pmod{p}$

设 $n=sp+q,m=tp+r$

易得 $(1+x)^{sp+q}\equiv{((1+x)^p)^s \cdot (1+x)^q} \equiv {(1+x^p)^s \cdot (1+x)^q} \equiv \sum\limits_{i=0}^sC_s^ix^{i \cdot p} \cdot \sum\limits_{j=0}^q C_q^jx^j \pmod{p}$

$\because \ $ 左边 $x^{tp+r}$ 的系数为 $C_{sp+q}^{tp+r}$，右边 $x^{tp+r}$ 的系数为 $C_s^t \cdot C_q^r$

$\therefore \ $ $C_{sp+q}^{tp+r} \equiv C_s^t \cdot C_q^r \pmod{p}$

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int qmi(int a,int b,int p)
{
    int res=1;
    while(b)
    {
        if(b&1) res=(LL)res*a%p;
        a=(LL)a*a%p;
        b>>=1;
    }

    return res;
}

//根据定义求即可
int C(int a,int b,int p)
{
    int res=1;
    for(int i=1,j=a;i<=b;i++,j--)
    {
        res=(LL)res*j%p;
        res=(LL)res*qmi(i,p-2,p)%p;
    }

    return res;
}

// c[a][b] = c[a % p][b % p] * c[a / p][b / p]
int lucas(LL a,LL b,int p)
{
    if(a<p&&b<p) return C(a,b,p);
    return (LL)C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}

int main()
{
    int n;
    cin>>n;

    cout<<

    while(n--)
    {
        LL a,b;
        int p;
        cin>>a>>b>>p;
        cout<<lucas(a,b,p)<<endl;
    }

    return 0;
}