数论板子

佚名 6年前 (2019-05-12) 随笔 1178人围观抢沙发百度已收录

基础三件套

ll exgcd(ll a,ll b,ll &x,ll  &y){
    if(!b) {
        x=1;y=0;
        return a;       
    }
    ll ret;
    ret=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return ret;
}

bool Equation(ll a,ll b,ll c,ll &x,ll &y){  //ax+by=c
    ll d=exgcd(a,b,x,y);
    if(c%d)return 0;
    x=c/d*x;y=c/d*y;
    return 1; 
}

ll inv(ll a,ll p){
    ll d,x,y;
    d=exgcd(a,p,x,y);
    if(d!=1) return -1;
    return (x+p)%p;
}