Templates for XCPC - 数学（一）

快速幂+快速求组合数

int fac[N],inv[N];
int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void init(){
    fac[0]=1;
    for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;
    inv[N-1]=qpow(fac[N-1],mod-2);
    for(int i=N-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int n,int k){
    if(k<0||k>n)return 0;
    return fac[n]*inv[k]%mod*inv[n-k]%mod;
}

求逆元

inline ll inv(ll x){return qpow(x,mod-2);}

exgcd

void exgcd(int a,int b,int &d,int &x,int &y){
    if(!b){d=a;x=1;y=0;}
    else{
        exgcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}

欧拉函数

int phi(int n) {
    int ans=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0) {
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}
int n,isp[N],phi[N];
vector<int> primes;
void get_phi(){
    for(int i=2;i<=n;i++)isp[i]=1;
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(isp[i]){
            primes.push_back(i);
            phi[i]=i-1;
        }
        for(int p:primes){
            if(i*p>n)break;
            isp[i*p]=0;
            if(i%p==0){
            // i的质因数分解中已经包含了p，
            // 由phi(n)=n*∏(1-1/p_i)，phi[i*p]=phi[i]*p
                phi[i*p]=phi[i]*p;
                break;
            }else{      //互质，利用欧拉函数的积性
                phi[i*p]=phi[i]*phi[p];
            }
        }
    }
}