Lucas--递归实现

//Lucas --递归实现 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll; //将longlong类型进行定义 
ll p; //定义一个素数p
ll fac[10000]; //定义一个数组F[i]=(i!)mod(p); 
void Init() //初始化数组 
{
    int i;fac[0]=1; //这里一定要定义注意 // for(i=1;i<=p;i++){
       fac[i]=fac[i-1]*i%p; }
}
ll Qpow_mod(ll base,ll expon)  //快速幂求模 
{
    ll sum=1;while(expon){
    if(expon&1) sum=sum*base%p;expon=expon>>1;base=base*base%p;}return sum;
}
ll C(ll n,ll m) //组合数C(n,m)
{
       if(m>n) return 0; return fac[n]*Qpow_mod(fac[m]*fac[n-m],p-2)%p;
} 
ll Lucas(ll n,ll m,int p)  //Lucas算法迭代实现 
{
      if(m==0) return 1;else return (C(n%p,m%p)*Lucas(n/p,m/p,p))%p;
}int main()
{
        ll n,m;//组合数的两个系数printf("Please put you n and m:\n");cin>>n>>m;printf("Please put you p:\n");cin>>p;Init();cout<<Lucas(n,m,p)<<endl;return 0; 
}