（数论）Lucas定理
Lucas定理内容：对于素数p，有 mod p =
*
mod p
来看代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool isprime(ll p){
if(p<=1) return false;
for(ll i=2;i<=sqrt(p);i++){
if(p%i==0){
return false;
}
}
return true;
}
ll work(ll n,ll p){
ll ans=1;
for(int i=1;i<=n;i++){
ans=ans*i%p;
}
return ans;
}
ll c(ll a,ll b,ll p){
if(b>a){
return 0;
}
return work(a,p)/work(b,p)/work(a-b,p);
}
ll lucas(ll a,ll b,ll p){
if(!isprime(p)){
cout<<"p is not a prime"<<endl;
return 0;
}
if(!b){
return 1;
}
return c(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
int main(){
ll ans=lucas(10,3,7);
cout<<ans;
return 0;
}