转载几篇感觉讲的好的题解
C函数讲的好的: C函数
lucas推导讲的好的: Lucas

题型:求$c_a^b \quad (mod p)d$
利用卢卡斯定理求解:$c_a^b=c_{a\%p}^{b\%p} \ast c_{\frac{a}{p}}^{\frac{b}{p}} \quad (mod \quad p)$

lucas公式求组合数 $\quad o(n \ast p \ast log_pa \ast logp)$

#include<iostream>
using namespace std;
typedef long long LL;
int quickPow(int a,int  b,int p)
{
    int t=1;
    while(b)
    {
        if(b&1) t=(LL)t*a%p;
        a=(LL)a*a%p;
        b>>=1;
    }
    return t;
}
int C(int a,int b,int p)
{
    if(b>a) return 0;
    int res=1;
    for(int i=a,j=1;j<=b;i--,j++)
    {
        res=(LL)res*i%p;//求a * (a-1) * .... * (a-b+1)
        printf("%d\n",i);
        res=(LL)res*quickPow(j,p-2,p)%p;//b的逆元
    }
    return res;
}
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;
    while(n--)
    {
        long long a,b,p;
        cin>>a>>b>>p;
        cout<<lucas(a,b,p)<<endl;
    }
}