数学

本文内容参考《算法导论》，OI Wiki。（数学好难，暂时搁置）

快速幂

例题

• P1226 【模板】快速幂。
• 509. 斐波那契数。

整数

时间复杂度：\(O(\log{n})\)。

private static final long MOD = 1_000_000_007;

private static long pow(long x, long n) {
    long res = 1L;
    for (; n != 0; x = x * x % MOD, n >>= 1) {
        if ((n & 1) == 1) {
            res = res * x % MOD;
        }
    }
    return res;
}

矩阵

时间复杂度：\(O(\log{n})\)。

private static final int MOD = 1_000_000_007;

private static long[][] pow(long[][] x, long n) {
    long[][] res = {{1, 0}, {0, 1}};
    for (; n != 0; x = mul(x, x), n >>= 1) {
        if ((n & 1) == 1) {
            res = mul(res, x);
        }
    }
    return res;
}

private static long[][] mul(long[][] a, long[][] b) {
    long[][] c = new long[2][2];
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
            }
        }
    }
    return c;
}

数论

例题

• 204. 计数质数。
• 2521. 数组乘积中的不同质因数数目。
• 2447. 最大公因数等于 K 的子数组数目。
• 1250. 检查「好数组」。

判断质数

时间复杂度 \(O(n\sqrt{n})\)。

private static boolean isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

质数筛法

埃氏筛

时间复杂度 \(O(n\log{\log{n}})\)，筛掉质数的倍数，每个合数都会被筛它的质因数的个数次。

private static boolean[] sieveOfEratosthenes(int n) {
    boolean[] np = new boolean[n + 1];
    np[0] = np[1] = true;
    
    for (int i = 2; i <= n / i; i++) {
        if (np[i]) continue;
        for (int j = i; j <= n / i; j++) {
            np[j * i] = true;
        }
    }
    return np;
}

欧拉筛

时间复杂度 \(O(n)\)，每个合数都只被它的最小质因数筛掉。

private static boolean[] sieveOfEuler(int n) {
    int cnt = 0;
    int[] p = new int[n + 1];
    boolean[] np = new boolean[n + 1];
    np[0] = np[1] = true;
    
    for (int i = 2; i <= n; i++) {
        if (!np[i]) p[cnt++] = i;
        for (int j = 0; p[j] <= n / i; j++) {
            np[p[j] * i] = true;
            if (i % p[j] == 0) break;
        }
    }
    return np;
}

分解质因数

时间复杂度 \(O(\sqrt{n})\)。

private static Map<Integer, Integer> primeFactors(int x) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 2; i <= x / i; i++) {
        while (x % i == 0) {
            x /= i;
            map.merge(i, 1, Integer::sum);
        }
    }
    if (x > 1) map.merge(x, 1, Integer::sum);
    return map;
}

欧拉函数

欧拉函数 \(\phi(n)\)，表示 \([1,n]\) 范围内和 \(n\) 互质的数的个数，有如下性质：

• 若 \(\gcd(a,b)=1\)，则 \(\phi(a\times b)=\phi(a)\times \phi(b)\)。
• 若 \(n=\prod_{i=1}^{k}{p_{i}^{c_{i}}}\)，其中 \(p_{i}\) 为质数，则 \(\phi(n)=n\times\prod_{i=1}^{k}(1-\frac{1}{p_{i}})\)。

我们可以使用分解质因数求解某个数的欧拉函数，时间复杂度为 \(O(\sqrt{n})\)；也可以使用欧拉筛来求解 \([1,n]\) 范围内所有数的欧拉函数，时间复杂度为 \(O(n)\)。在欧拉筛中，每个合数都是被它的最小质因子筛掉，设 \(p\) 是 \(n\) 的最小质因子，则 \(n=n^{\prime}\times p\)，分类讨论：

• 如果 \(n^{\prime}\bmod p\neq 0\)，因为 \(p\) 是质数，所以 \(\gcd(n^{\prime},p)=1\)，则 \(\phi(n)=\phi(n^{\prime})\times \phi(p)=\phi(n^{\prime})\times (p-1)\)。
• 如果 \(n^{\prime}\bmod p=0\)，则 \(\phi(n)=p\times n^{\prime}\times\prod_{i=1}^{k}(1-\frac{1}{p_{i}})=p\times \phi(n^{\prime})\)。

private static int[] sieveOfEuler(int n) {
    int cnt = 0;
    int[] p = new int[n + 1];
    int[] phi = new int[n + 1];
    boolean[] np = new boolean[n + 1];
    phi[1] = 1;
    np[0] = np[1] = true;

    for (int i = 2; i <= n; i++) {
        if (!np[i]) {
            p[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; p[j] <= n / i; j++) {
            np[p[j] * i] = true;
            if (i % p[j] == 0) {
                phi[p[j] * i] = p[j] * phi[i];
                break;
            }
            phi[p[j] * i] = (p[j] - 1) * phi[i];
        }
    }
    return phi;
}

最大公约数

欧几里得算法

时间复杂度 \(O(\log{\max(a,b)})\)。求得最大公约数之后，使用 \(\gcd(a,b)\times\operatorname{lcm}(a,b)=a\times b\) 公式可以得到最小公倍数。

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

扩展欧几里得算法

常用于求解 \(ax+by=\gcd(a,b)\) 的一组解。

private static int x, y;

private static int exgcd(int a, int b) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b);
    int t = x - a / b * y;
    x = y;
    y = t;
    return d;
}

其他知识

约数个数

若 \(n=\prod_{i=1}^{k}{p_{i}^{c_{i}}}\)，则 \(d_{n}=\prod_{i=1}^{k}(c_{i}+1)\)。

约数之和

若 \(n=\prod_{i=1}^{k}{p_{i}^{c_{i}}}\)，则 \(s_{n}=\prod_{i=1}^{k}\sum_{j=0}^{c_{i}}{p_{i}^{j}}\)。

裴蜀定理

若 \(a,b\) 是整数，则对于任意的整数 \(x,y\)，\(ax+by\) 总是 \(\gcd(a,b)\) 的倍数，并且存在整数 \(x,y\)，使得 \(ax+by=\gcd(a,b)\)。特别的，若存在整数 \(x,y\) 使得 \(ax+by=1\)，则 \(\gcd(a,b)=1\)，即 \(a,b\) 互质。

费马小定理

若 \(p\) 是质数，\(\gcd(a,p)=1\)，则 \(a^{p-1}\equiv 1\pmod{p}\)。

欧拉定理

若 \(\gcd(a,n)=1\)，则 \(a^{\phi(n)}\equiv 1\pmod{n}\)。

模乘法逆元

若 \(p\) 是质数，根据费马小定理，有 \(a\times a^{-1}\equiv 1\equiv a^{p-1}\pmod{p}\)，得到 \(a^{-1}\equiv a^{p-2}\pmod{p}\)。

若 \(b\) 是任意整数，求 \(a\) 的逆元，等价于求 \(ax\equiv 1\pmod{b}\) 的解，等价于求 \(ax+by=1\) 的解。如果 \(\gcd(a,b)=1\)，则可以使用扩展欧几里得算法求解该方程。如果 \(\gcd(a,b)\neq 1\)，根据裴蜀定理可知方程无解（或者可以将方程变换为 \(\frac{a}{g}x+\frac{b}{g}y=\frac{1}{g}\)，等式左边是整数，右边不是整数，方程无解），即逆元不存在。

线性同余方程

求 \(ax\equiv c\pmod{b}\) 的解，等价于求 \(ax+by=c\) 的解，同样的，当 \(\gcd(a,b)\mid c\) 时方程有解。使用扩展欧几里得算法可以求出 \(ax+by=\gcd(a,b)\) 的解，然后将方程变换为 \(a\frac{c}{\gcd(a,b)}x_{0}+b\frac{c}{\gcd(a,b)}y_{0}=c\)，可以得到方程的解。