[数论] 常用数论模板（一）

欧几里得算法

可以用来求解两个数 x 和 y 的最大公约数和最小公倍数( x*y/gcd(x,y) )

int gcd(int a,int b){
    if(!b)
        return a;
    return gcd(b,a%b);
}

扩展欧几里得算法

可以用来求解不定方程 ax + by = gcd(a,b) 的一组解(x0,y0) ，以及其他各组解(x0+kb’,y0-ka’)
[a’ = a/gcd(a,b) b’ = b/gcd(a,b)]

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

快速幂(取模)

int ksm(int a,int b,int mod){
    int ans = 1;
    int base = b%mod;

    while(b){
        if(b&1)
            ans = (ans*base)%mod;
        b>>1;
        base=(base*base)%mod;
    }
    return ans;
}