快速幂#

快速幂主要是能在 $O(log k)$ 的时间复杂度求解 $a^k \% m$ 。其思路在于任何一个数都可以写成以下形式 $k=2^{c_1} + 2^{c_2} + \cdots + 2^{c_y}$ 。{$c_i$} 序列是严格单调递增的。因此 $a^k \ \% \ m$ 可以写成 $a^{2^{c_1} + 2^{c_2} + \cdots + 2^{c_y}} \ \% \ m$ ，从而一步一步往下计算 $a^{2^{c_i}}$ ，最多计算 $logk$ 次即可。

核心代码如下 ：

1
int kpow(int a, int k, int m) {
2

3
    a %= m;
4
    int ans = 1 % m;
5
    while (k) {
6
        if (k & 1) ans = (LL) ans * a % m;
7
        k >>= 1;
8
        a = (LL) a * a % m;
9
    }
10
    return ans;
11
}

龟速乘#

龟速乘主要是 $O(logb)$ 的时间内计算 $a*b$，这种计算方法主要应用在 $a*b$会爆掉 long long 的情况下，思路和快速幂一致，也是利用 $b$ 的二进制拆分。

核心代码如下：

1
LL kmul(LL x, LL y, LL m) {
2
    LL ans = 0;
3
    while (y) {
4
        if (y & 1) ans = (ans + x) % m;
5
        x = (x + x) % m;
6
        y >>= 1;
7
    }
8
    return ans;
9
}

试除法#

时间复杂度：$\mathcal{O}(\sqrt{n})$ 当 $n \le 10^{12}$ 时，足够判断 代码如下：

1
bool is_prime(int x) {
2

3
    if (x == 1) return false;
4
    for (int i = 2; i <= x / i; i ++ )
5
        if (x % i == 0) return false;
6
    return true;
7
}

另外，这个方法还可以加快速度，根据[[#唯一分解定理]]，只需要使用 $[2,\sqrt n]$ 里面的素数来判断即可。 因此，这里有个策略是利用线性筛提前预处理好前 $\sqrt n$ 的所有素数，但由于时间和空间限制，这个 $n$ 的范围最大是 $n \le 10^{14}$ 代码如下：

1
bool is_prime(int x) {
2

3
    if (x == 1) return false;
4
    for (int i = 0; prime[i] <= x / prime[i]; i ++ )
5
        if (x % prime[i] == 0) return false;
6
    return true;
7
}

Miller-Rabin 算法#

1
#include <random>
2
random_device rd;
3
mt19937 gen(rd());
4

5
int kpow(int a, int k, int m) {
6

7
    a %= m;
8
    int ans = 1;
9
    while (k) {
10
        if (k & 1) ans = (LL) ans * a % m;
11
        k >>= 1;
12
        a = (LL) a * a % m;
13
    }
14
    return ans;
15
}
16

17
bool witness(int a, int n) {
18
    int u = n - 1, t = 0;
19
    while ((u & 1) == 0) u >>= 1, t ++ ;
20
    int x1, x2;
21
    x1 = kpow(a, u, n);
22
    for (int i = 0; i < t; i ++ ) {
23
        x2 = kpow(x1, 2, n);
24
        if (x2 == 1 && x1 != 1 && x1 != n - 1) return true;
25
        x1 = x2;
26
    }
27
    if (x1 != 1) return true;
28
    return false;
29
}
30

31
bool miller_rabin(int n, int s) {
32

33
    if (n < 2) return false;
34
    if (n == 2) return true;
35
    if (n % 2 == 0) return false;
36
    // i < min(s, n)，因为随机数取的是 [1,n-1]，当 s > n 时没啥意义
37
    for (int i = 0; i < s && i < n; i ++ ) {
38
        int a = gen() % (n - 1) + 1;
39
        if (witness(a, n)) return false;
40
    }
41
    return true;
42
}

唯一分解定理#

任何 $n\ge 2$ 的整数都可以分解成若干个质数乘积。也就是说

质因数分解#

思路：首先利用一个数 $n$ 的质因数中大于 $\sqrt n$ 的最多只有一个的特性，只需要枚举到 $\sqrt n$ 的情形就行，枚举的过程中，$n$ 可以通过枚举到的质因数逐渐变小，最后退出循环后，只要 $n$ 仍旧大于 1，说明这是剩下来的那个质因数。 时间复杂度：$\mathcal{O}(\sqrt{n})$ 代码如下：

1
void divide(int x) {
2
    for (int i = 2; i <= x / i; i ++ ) {
3
        int cnt = 0;
4
        while (x % i == 0) cnt ++ , x /= i;
5
        if (cnt) cout << i << ' ' << cnt << endl;
6
    }
7
    if (x > 1) cout << x << ' ' << 1 << endl;
8
}

另外，当 $n$ 的范围不是很大的时候，也就是 $10^7$ 左右的时候，可以通过只枚举素数来加快速度。时间复杂度大概是 $\mathcal{O}(\sqrt{\frac{n}{ln n}})$

代码如下：

1
void divide(int n) {
2

3
    for (int i = 0; primes[i] <= n / primes[i]; i ++ ) {
4
        int cnt = 0;
5
        while (n % primes[i] == 0) cnt ++ , n /= primes[i];
6
        if (cnt > 0) {
7
            cout << primes[i] << ' ' << cnt << endl;
8
        }
9
    }
10
    if (n > 1) cout << n << ' ' << 1 << endl;
11
}

另外，如果要存的话，使用差不多 100 大小的数组就能存，因为对于 int 型的数质因数最多有十几个，一个因数的个数最多有三十几个

勒让德定理#

在正数 $n!$ 的质因数分解中，质数 $p$ 的指数记作 $v_p(n!)$ ，则$v_p(n!)=\sum_{k\ge 1}\lfloor \frac{n}{p_k} \rfloor$

阶乘质因数分解#

思路就是唯一分解定理和勒让德定理的应用。 时间复杂度在 $O(n)$ 左右。 代码如下：

1
// 首先是找质数，根据上面的线性筛
2

3
// 然后就是勒让德计算
4
for (int i = 0; i < cnt; i ++ ) {
5
        int cnt = 0;
6
        for (int k = n / primes[i]; k > 0; k /= primes[i]) cnt += k;
7
        cout << primes[i] << ' ' << cnt << endl;
8
    }

威尔逊定理#

若 $p$ 为素数，则 $p$ 可以整除 $(p-1)!+1$ 威尔逊定理四种表示方法：

1. $((p-1)!+1)\text{mod} \ p = 0$
2. $(p-1)!\text{mod} \ p = p-1$
3. $(p-1)!=pq - 1$ ，$q$ 为正整数
4. $(p-1)!\equiv -1(\text{mod} \ p)$ 核心记住第一点

约数相关性质#

• 约数个数 根据唯一分解定理，约数个数 $f(n)=(x_1+1)*(x_2+2)*\cdots*(x_k+1)$ 那么前 $n$ 个数的约数个数之和怎么算呢，可以根据第 $i$ 个数在 $1-n$ 中是多少个数的约数，也就是 $\frac{n}{i}$ 个，因此 $\sum f(i) = nln n$ 大概是这个量级。这对分析时间复杂度有帮助。

• 约数之和 一个数所有约数之和为 $\text{sum}=(1+p_1^1 + \cdots + p_1^{x_1}) * (1+p_2^1 + \cdots + p_2^{x_1}) * \cdots * (1+p_k^1 + \cdots + p_k^{x_k})$ ，这个很容易证明，根据乘法分配法，最后加法分隔开的每个数，都是从每个括号里面选择一个数进行相乘，这样刚好就枚举了所有的约数可能。 代码如下：

  1
  // 第一步分解质因数
  2
  int ans = 1;
  3
  for (auto [u, v]: um) {
  4
      int p = 1, t = 0;
  5
      for (int i = 0; i <= v; i ++ ) t = (t + p) % MOD, p = 1ll * p * u % MOD;
  6
      ans = 1ll * ans * t % MOD;
  7
  }
  

• 最多的约数个数 在 int 范围内，约数个数最多的数大概有 1600 个约数。这对分析时间复杂度相当有帮助。

• 快速求出所有约数 首先第一步，对数先进行质因数分解，然后 dfs 求得所有约数，根据上述的最多约数个数为 1600 个左右，因此 dfs 的时间一般来说是小于质因数分解的速度的。因此，求所有约数的时间极限变成了如何快速求质因数分解。[[#质因数分解]] 其中，dfs 代码为

  1
  void dfs(int cur, int val) {
  2
  if (cur >= idx) {
  3
      res.push_back(val);
  4
      return ;
  5
  }
  6
  for (int i = 0, t = 1; i <= c[cur]; i ++ , t *= p[cur])
  7
      dfs(cur + 1, val * t);
  

} ```

1
LL gcd(LL a, LL b) {
2
    return b ? gcd(b, a % b) : a;
3
}

扩展欧几里得求二元线性丢番图的特解#

首先利用扩展欧几里得求方程 $ax+by=gcd(a,b)$ 的特解，代码如下

1
LL exgcd(LL a, LL b, LL &x, LL &y) {
2
    if (b == 0) {
3
        x = 1, y = 0;
4
        return a;
5
    }
6
    LL d = exgcd(b, a % b, y, x);
7
    y -= a / b * x;
8
    return d;
9
}

那么可以根据这个来求 $ax+by=c$ 的特解

1. 判断 $c$ 是否整数 $gcd(a,b)$
2. 求$ax+by=gcd(a,b)$ 的特解 $(x_0, y_0)$
3. 在 $ax_0+by_0=gcd(a,b)$ 两边乘 $c / gcd(a,b)$ ，可得特解为 $(x_0^\prime, y_0^\prime)=(x_0 * c / gcd(a,b), y_0 * c / gcd(a,b)$
4. 通解为 $x=x_0^\prime + (b/d)n, y=y_0^\prime-(a/d)n$，其中 $d=gcd(a,b)$

一元线性同余方程#

求解 $ax\equiv b (\text{mod} \ m)$ ，这个同余方程等价于二元丢番图方程，方程有解

定理 设 $a,b$ 和 $m$ 是整数，$m>0,gcd(a,m)=d$。若 $d$ 不能整除 $b$，则 $ax \equiv b (\text{mod} \ m)$ 无解；若 $d$ 能够整除 $b$ ，则 $ax \equiv b (\text{mod} \ m)$ 有 $d$ 个模 $m$ 不同余的解

推论 $a,m$ 互素，线性同余方程 $ax \equiv b (\text{mod} \ m)$ 有唯一的模 $m$ 不同余的解。

逆#

给定整数 $a$，且满足 $gcd(a,m)=1$，则 $ax \equiv 1 (\text{mod} \ m)$ 的一个解为 $a$ 模 $m$ 的逆，记为 $a^{-1}$

中国剩余定理#

假设有 $m_1,m_2,\cdots, m_n$ 两两互质 ，且

那么该方程有一个通用解 设 $M = m_1 * m_2 * \cdots * m_n$ , $M_i = M / m_i$ 因此 $M_i$ 一定与 $m_i$ 互质，故M, M设 $M_i^{-1}$ 为 $M_i$ 模 $m_i$ 的逆元 因此可以构造答案

可以验证此 $x$ 成立

1
LL calc() {
2

3
    LL a1 = a[1], m1 = m[1];
4
    for (int i = 2; i <= n; i ++ ) {
5
        LL a2 = a[i], m2 = m[i];
6
        LL a = a1, b = a2, c = (m2 - m1 % a2 + a2) % a2;
7
        LL x, y;
8
        LL d = exgcd(a, b, x, y);
9
        if (c % d) return -1;
10
        // b0 的计算也可以龟速乘
11
        LL k = b / d, b0 = (c / d * x % k + k) % k;
12
        LL ans = a1 * k;
13
        // 下面这行可能爆longlong 不行就龟速乘
14
        m1 = (a1 * b0 % ans + m1) % ans;
15
        a1 = ans;
16
    }
17
    return m1;
18
}

线性筛求欧拉函数#

欧拉函数可以用筛素数的写法来计算欧拉函数，线性筛的本质是用一个数的最小质数将其筛掉，那么便可以思考一个数的欧拉函数值是否可以通过其最小质数和其相应约数计算得到。

首先，对于 $n$ 为质数，那么 $\phi(n)$ 为 $n-1$。

然后思考线性筛的过程，如果 $i \% primes[j] == 0$ 时，会发生什么，对于 $i*primes[j]$ 来说，$primes[j]$ 就是它的最小质数，但是事实上此时 $primes[j]$ 是$i$ 的约数了，根据欧拉函数与指数没有关系，假设，$\phi(i) = i * x$，那么 $\phi(i*primes[j]) = i * primes[j] * x = primes[j] * phi(i)$。

如果 $i \% primes[j] != 0$ 时，则说明 $i$ 的质因数分解中原来没有 $primes[j]$，此时 $phi(i) = i*x$，那么 $phi(i*primes[j])=i * primes[j] * \frac{primes[j] - 1}{primes[j]} * x = (primes[j] - 1) * phi(i)$ 。

核心代码如下：

1
oid get_euler(int n) {
2

3
    for (int i = 2; i <= n; i ++ ) {
4
        if (!st[i]) {
5
            primes[cnt ++ ] = i;
6
            phi[i] = i - 1;
7
        }
8
        for (int j = 0; i <= n / primes[j]; j ++ ) {
9
            st[i * primes[j]] = true;
10
            if (i % primes[j] == 0) {
11
                phi[i * primes[j]] = phi[i] * primes[j];
12
                break;
13
            }
14
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
15
        }
16
    }
17
}

欧拉定理#

设 $a,m \in N^+$, 且 $gcd(a,m)=1$，$\phi(x)$ 为欧拉函数，有

欧拉降幂#

莫比乌斯函数#

根据[[#唯一分解定理]]

若 $F(n)=\sum_{n | d} f(d)$，则 $f(n)=\sum_{n|d} \mu (\frac{d}{n})F(d)$

矩阵快速幂的应用#

对于 $f(n)=f(1)+f(2)+\cdots+f(n-1) + c$ 这样的递推式子，容易构造矩阵

其中，矩阵 $A$ 就是根据递推式构造的矩阵 有的时候，递推式就是根据动态规划转移式子得来，有的时候隐藏的很深，需要去发现去设计

高斯消元求解线性方程组#

代码如下：

1
/*
2
输出解 注意 0 的判断
3
for (int i = 1; i <= n; i ++ )
4
    printf("%.3f ", fabs(a[i][n + 1]) < eps ? 0.000 : a[i][n + 1]);
5
*/
6
// 0 无解 1 唯一解 2 无穷解
7
int guass() {
8

9
    int row, col;
10
    for (col = 1, row = 1; col <= n; col ++ ) {
11
        int t = row;
12
        for (int i = row + 1; i <= n; i ++ )
13
            if (fabs(a[i][col]) > fabs(a[t][col]))
14
                t = i;
15

16
        if (fabs(a[t][col]) < eps) continue;
17
        for (int i = col; i <= n + 1; i ++ ) swap(a[t][i], a[row][i]);
18
        for (int i = n + 1; i >= col; i -- ) a[row][i] /= a[row][col];
19

20
        for (int i = 1; i <= n; i ++ )
21
            if (i != row && fabs(a[i][col]) > eps) {
22
                for (int j = n + 1; j >= col; j -- ) a[i][j] -= a[row][j] * a[i][col];
23
            }
24

25
        row ++ ;
26
    }
27
    if (row <= n) {
28
        for (int i = row; i <= n; i ++ )
29
            if (fabs(a[i][n + 1]) > eps) return 0;
30
        return 2;
31
    }
32
    return 1;
33
}