基础数论 | OI笔记

最大公约数(gcd)

使用辗转相除法求解

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

或简化写法

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
    //or return b == 0 ? a : gcd(b, a % b);
}

最小公倍数(lcm)

原理

• 最小公倍数可理解为去除两个数一个公共因数之后的乘积
• 最大公因数可理解为两个数公共因数的乘积
• 这样就容易得到两者乘积为这两个数的乘积

$$\text{gcd}(a, b) * \text{lcm}(a, b) = a * b$$

• 由此即可得到
  $$\text{lcm}(a, b) = \frac{a * b}{\text{gcd}(a, b)}$$

代码实现

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}

素数

线性筛

int primes[N], cnt; //primes存储所有素数
bool st[N]； //st[x]存储x是否被筛掉

void get_primes(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i])
            primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0)
                break;
        }
    }
}

快速幂

求$m ^ k \pmod p$，时间复杂度为$O(\log{k})$

int qpow(int m, int k, int p)
{
    int res = 1 % p, t = m;

    while(k)
    {
        if(k & 1)
            res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }

    return res;
}