欧几里得算法-最大公约数-$O(log{n})$

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

算术基本定理

对任意正整数N，均有 $N = P{1}^{d{1}} * P{2}^{d{2}} * … * P{n}^{d{n}}$
其中 $P{i}$为质数, $d{i}$ 大于0
N的约数的个数= (d1 + 1)(d2 + 1)…(dn + 1)
约数之和= (1+p1^1 + … + p1^d1)(1+p2^1 + … + p2^d2) … (1+pn^1 + … + pn^dn)

线性筛算法

int prime[N], minp[N], mark[N]; // prime存所有质数，minp存每个数的最小质因子，mark标记是否为合数，1合
int cnt;
void get_prime(int n) {
    for (int i = 2; i <= n; i++) {
        if (!mark[i]) prime[cnt++] = i, minp[i] = i;
        for (int j = 0; i * prime[j] <= n; j++) {   // N > n
            mark[prime[j] * i] = 1;  //合数标记
            minp[prime[j] * i] = prime[j];
            if (i % prime[j] == 0) break;  //每个合数一定使用其最小质因子筛掉的，保证唯一性
        }
    }
}

扩展欧几里得算法-求a-b最大公因数d，以及ax+by=d的系数

int exgcd(int a, int b, int &x, int &y) {  //a对应x，b对应y
    if (!b) {
        x = 1, y = 0;
        return a;
    }

    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;   //这里由于b系数变了，需要重新计算
    return d;   //返回最大公因数
}