Lucas定理

Lucas定理，是用来求C_m_n%p的

C_m_n=C_m%p_n%p*C_m/p_n/p%p;

代码:

#include<bits/stdc++.h>
using namespace std;
long long t,n,m,p;
long long ksm(long long x,long long y,long long p){
    long long ans=1;
    while(y){
        if(y&1)ans=(ans*x)%p;
        x=(x*x)%p;
        y>>=1;
    }
    return ans;
}
long long C(long long n,long long m,long long p){
    if(m>n)return 0;
    long long x=1,y=1;
    for(long long i=1;i<=m;i++)x=(x*(n-i+1))%p,y=(y*i)%p;
    return (ksm(y,p-2,p)*x)%p;
}
long long Lucas(long long n,long long m,long long p){
    if(!m)return 1;
    return C(n%p,m%p,p)*Lucas(n/p,m/p,p);
}
int main(){
    cin>>t;
    while(t--){
    cin>>n>>m>>p;
    cout<<Lucas(n,m,p)<<endl;    
    }
    return 0;
}