GCD：最大公约数

时间复杂度：$O(logN)$

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

6015. 统计可以被 K 整除的下标对数目

$x*y \% k = 0$，已知$x和k$，那么$y$必须满足为$\frac{k}{gcd(k, x)}$的倍数

最小公倍数：LCM

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

质因数分解

时间复杂度：$O(\sqrt N)$

public List<Integer> get(int n) {
    List<Integer> res = new ArrayList<>();
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i = 0) n /= i;
            res.add(i);
        }
    }
    if (n != 1) res.add(n);
    return res;
}