柒葉灬 的博客

柒葉灬 的博客

数论板子

posted on 2019-08-14 20:29:45 | under 板子 |

扩展欧几里得

int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int r=exgcd(b,a%b,x,y);
    int p=y;
    y=x-(a/b*y);
    x=p;
    return r;
}

中国剩余定理

const int maxn=15;
struct CRT{
    int id;
    int a[maxn],m[maxn];
    long long lcm;
    CRT(){lcm=1;}
    void insert(int ai,int mi){
        a[++id]=ai;
        m[id]=mi;
        lcm*=mi;
    }
    long long exgcd(long long a,long long b,long long &x,long long &y){
        if(b==0){
            x=1;
            y=0;
            return a;
        }
        long long r=exgcd(b,a%b,x,y);
        long long p=y;
        y=x-(a/b*y);
        x=p;
        return r;
    }
    long long qtime(long long a,long long b,long long P){
        long long res=0;
        while(b){
            if(b&1)res=(res+a)%P;
            b>>=1;
            a=(a+a)%P;
        }
        return res;
    }
    long long solve(){
        long long res=0;
        for(int i=1;i<=id;i++){
            long long x,y;
            exgcd(lcm/m[i],m[i],x,y);
            while(x<0)x+=m[i];
            long long tmp=qtime(lcm/m[i],qtime(x,a[i],lcm),lcm);
            res=(res+tmp)%lcm;
        }
        return res;
    }
}crt;

lucas定理

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1e5+100;
int n,m,P;
long long qpow(long long p,long long q){
    long long res=1;
    while(q){
        if(q&1)res=res*p%P;
        p=p*p%P;
        q>>=1;
    }
    return res;
}
long long f[maxn],fr[maxn];
void init(){
    f[0]=fr[0]=1;
    for(int i=1;i<=P;i++)
        f[i]=f[i-1]*i%P;
    fr[P-1]=qpow(f[P-1],P-2);
    for(int i=P-2;i>=1;i--)
        fr[i]=fr[i+1]*(i+1)%P;
}
long long C(int a,int b){
    if(a<b)return 0;
    return f[a]*fr[b]%P*fr[a-b]%P;
}
long long lucas(int a,int b){
    if(b==0)return 1;
    return lucas(a/P,b/P)*C(a%P,b%P)%P;
}
int main(){
    for(int _=(cin>>_,_);_--;){
        cin>>n>>m>>P;
        init();
        cout<<lucas(n+m,m)<<endl;
    }
    return 0;
}