快速模拟暴力组合数

#include<bits/stdc++.h>//笔者懒,用的万能头文件~
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){//特判一下
        return 0;
    }
    if(n-m>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;
}