本题解讲的是快速暴力组合数的方法，需要知道以下知识(能做此题的大佬应该都知道吧。。。)：

欧拉筛，组合数公式,卡速米(这个应该没人会吧？) 否则将引起不适

设π(x->y)为从x连乘到y(数学公式编译器崩了。。。)

组合数，大家都知道，公式为C(n,m)=!n/(!m*!(n-m)) 我们将它化简一下:π(m+1->n)/!(n-m)(当然,如果n-m>m,我们可以将m替换为n-m进行优化)

然后，我们手算是将所有数列举出来再一一 **约分** ，

我们知道，约分就是约掉分子分母的公因数，

那么如果我们将分子分母的数全部转换成几个质数相乘的形式，然后统计每个质数的个数，再加个快速幂，不就可以高效的解出来了吗？

那么，我们该如何分解质因数呢？

答案是：欧拉筛求最小质因数！！

我们可以用欧拉筛求出x的最小质因数，然后用个while，直到x==1时结束，以下为代码：

#include
     
      //笔者懒,用的万能头文件~    using namespace std;    const int N=1e5+1;//范围    int f[N],zhi[N>>1],hav[N],e;//质数表其实不用开那么大,反正少一半是没毛病的(除偶数)    inline void oula(int maxe){        for(int i=2;i<=maxe;++i){            if(!f[i]){
   //如果没被筛过(质数)                f[i]=i;//质数的最小质因数是它本身                zhi[++e]=i;//质数表            }            for(int j=1;j<=e;++j){                if(i*zhi[j]>maxe){
   //如果超出范围                    break;//退出                }                f[i*zhi[j]]=zhi[j];//标记最小质因数为zhi[j],注意千万不要写i,虽然i也是i*zhi[j]的因数,但i不一定是质数！！                if(i%zhi[j]==0){
   //欧拉筛速度快的关键。。。                    break;                }            }        }    }    inline int ksc(int x,int y,int p){
   //快速乘        int ans=0;        while(y){            if(y&1){                ans+=x;                ans%=p;            }            x+=x;            x%=p;            y>>=1;        }        return ans%p;    }    inline int ksm(int x,int y,int p){
   //快速幂        int ans=1;        while(y){            if(y&1){                ans=ksc(ans,x,p);            }            x=ksc(x,x,p);            y>>=1;        }        return ans%p;//这里记得模p,不然有的时候可能会错    }    inline void up(int x){
   //分解做分子        while(x>1){            hav[f[x]]++;            x/=f[x];        }    }    inline void down(int x){
   //分解做分母        while(x>1){            hav[f[x]]--;            x/=f[x];        }     }    inline int C(int n,int m,int p){        if(n
      
       m){            m=n-m;//小优化        }        for(int i=m+1;i<=n;++i){            up(i);//将i质因数分解作为分子        }        for(int i=2;i<=n-m;++i){            down(i);//将i质因数分解作为分母        }        int ans=1;        for(int i=1;i<=e;++i){
   //枚举每一个质数            if(hav[zhi[i]]){
   //如果结果中出现了第i个质数                ans=ksc(ans,ksm(zhi[i],hav[zhi[i]],p),p);                hav[zhi[i]]=0;//记得清空            }        }        return ans;    }    int main(){        oula(N-1);//欧拉筛求最小质因数,由于之前加了1所以这里要减1        int n,m,p;        scanf("%d%d%d",&n,&m,&p);//输入        printf("%d",C(n,m,p));        return 0;    }
      
     

至于本题，只需要将这个快速暴力组合数的方法代个卢卡斯定理就行了~(虽然直接算甚至还快些,不过如果n和m再大点就必须用卢卡斯了,亲测直接暴力+o2 98ms 不加o2 123ms)