数论

试除法判定质数

关于

一个数的因数都是成对出现的，例如12的因数有3和4，2和6

成对的因数中，较小的那个肯定不会超过 $\sqrt{n}$ 吧

36 的因数对：$<1, 36> <2, 18> <3, 12> <4, 8> <6, 6>$

所以只需要枚举较小的那个，$i * i \le n$，但是这样在C++中会溢出，把一个 $i$ 丢到除数下就好了 $i \le \frac{i}{n}$

bool check(int x){
    if (x < 2) return false;
    for (int i = 2; i <= x / i; ++ i) {
        if (x % i == 0) return false;
    }
    return true;
}

分解质因数

关于

任何一个数，都可以表示成很多个质因数相乘 $10 = 2 * 5$

$x$ 是不断变小的，算法得考虑跳出循环后的 $x$，如果这个 $x$ 不等于 $1$，那么还得算一个结果。

比如 $\sqrt{6} \approx 2.2449$ ，但它有个因数是 $3$

void divide(int x) {
    for (int i = 2; i <= x / i; ++ i) {
        if (x % i == 0) {  // 如果是质因数
            int cnt = 0;   // 求其指数 
            while(x % i == 0) {
                cnt ++;
                x /= i;
            }
            cout << i << " " << cnt << endl;
        }
    }

    // x 是不断变小的
    // 在这里如果 x > 1, 说明跳出循环后还有一个质因数
    if (x > 1) cout << x << " " << 1 << endl;
}

试除法求所有因数

关于

与求质因数方法大同小异，所有因数都是成对出现的，只需要枚举小的那个。

需要注意的是，像 36 / 6 = 6 ，必须得特殊判别一下，否则会将两个 6 加入到结果集中

void divide (int x) {
    for (int i = 1; i <= x / i; ++ i) {
        if (x % i == 0) {
            v.push_back(i);
            if (x / i != i) v.push_back(x / i);
        }
    }
    sort(v.begin(), v.end());
}

约数个数

关于

举个例子，将 $6$ 写成质因数相乘的形式：$6 = 2 * 3$ 。接着给他们加上指数 $6 = 2^1 * 3^1$

或许能猜到，质因数指数取不同值的时候，对应的乘积结果就是一个因数

当 $2$ 和 $3$ 的指数进行全排列时，就能得到 $6$ 不同的因数

map<int, int> cnt;
map<int, int>::iterator it;

// 求x因数的指数
void divide_sum (long long x) {
    for (long long i = 2; i <= x / i; ++ i) {
        while (x % i == 0) {
            cnt[i] ++;
            x /= i;
        }
    }
    if (x > 1) cnt[x] ++;
}

// 求因数之和
long long get_res(){
    long long res = 1;
    for (it = cnt.begin(); it != cnt.end(); ++ it) {
        // 这里+1是因为多一种选取方式
        // 例如：2^1，那么 2 的指数可以选 0 也可以选 1
        // 例如：3^4，那么 3 的指数可以选 0, 1, 2, 3, 4
        res = res * (it->second + 1) % MOD;
    }
    return res;
}

约数之和

如果是求单个数的因数之和，可以用上面那种方式，但是如果需要求多个数的乘积的约数之和，就需要一些巧妙的方式

关于

设 $p_1$ ~ $p_k$ 是不同的质因数，那么因数之和就是下面这个式子的乘积。（我不是很想写公式，但是这样表示确实比较快一点......）

$$(p_1^0 + p_1^1 + ... + p_1^n) * ... * (p_k^0 + p_k^1 + ... + p_k^n)$$

注意那些加粗的行，以 $2^3$ 为例，实际的意义是

$T = 1 + 2^1 + 2^2 + 2^3$

$T = 1 + 2 \times (1 + 2^1 + 2^2)$

$T = 1 + 2 \times (1 + 2 \times (1 + 2))$

// 求各质因数的指数代码同上
// 求因数之和
long long get_res(){
    long long res = 1;
    for (it = cnt.begin(); it != cnt.end(); it ++) {
        // p是质因数，e是对应的指数
        int p = it->first, e = it->second;
        // 开始求一个括号里的和
        long long t = 1;
        while (e -- ) t = (t * p + 1) % MOD;
        // 括号求和结束
        res = res * t % MOD;
    }
    return res;
}

约数的总结

tip

如果 $N = p_1c_1∗p_2c_2∗…∗p_kc_k$

约数个数：$(c_1+1)∗(c_2+1)∗…∗(c_k+1)$

约数之和：$(p_1^0+p_1^1+…+p_1^{c_1})∗…∗(p_k^0+p_k^1+…+p_k^{c_k})$

最大公约数 & 最小公倍数

关于

这么优美的算法不背一下吗？ gcd(a, b) 求的是最大公约数

最小公倍数就是 a * b / gcd(a, b)

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

求组合数

写在前面

从10个球里面选3个红球。$C_{10}^3 = \frac{10 \times 9 \times 8}{3 \times 2 \times 1}$

有一递推公式 $C_n^a = C_{n-1}^a + C_{n-1}^{a-1}$。

例：对于第一个红球，如果选了它，那么就下来就只用再选两个红球$C_{9}^{2}$。

如果没有选它，那么就下来还需要选3个红球$C_{9}^{3}$

所以 $C_{10}^{3} = C_9^2 + C_9^3$

特殊的，如果从10个球中选择0个红球，那么只能有一种选法 $C_{10}^0 = 0$

int c[N][N]; // c[i][j]代表从i个球里面选j个红球

void init(){
    c[0][0] = 1;
    for (int i = 1; i <= 2000; ++ i) {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++ j) { // 注意j的边界
            c[i][j] = c[i-1][j] + c[i-1][j-1];
        }
    }
}

快速幂求逆元

当 $n$ 为质数时，可以用快速幂求逆元：

$$\frac{a}{b} ≡ a * x (mod \ n)$$

两边同乘 $b$ 可得

$$a ≡ a * b * x (mod \ n)$$

即

$$1 ≡ b * x (mod \ n)$$

同

$$b * x ≡ 1 (mod \ n)$$

由费马小定理可知，当 $n$ 为质数时

$$b^{(n - 1)} ≡ 1 (mod \ n)$$

拆一个 $b$ 出来可得

$$b * b^{(n - 2)} ≡ 1 (mod \ n)$$

故当 $n$ 为质数时，$b$ 的乘法逆元

$$x = b ^{(n - 2)}$$