素数判定#

如何判定正整数 $n$ 是否是素数?

很容易想到用每一个小于 $n$ 且大于 $1$ 的数来判断它是否是 $n$ 的约数, 若都不是, 则 $n$ 为素数, 否则为合数.

这个暴力算法是 $\mathcal{O}(n)$ 的, 但是我们考虑到, 若数 $p$ 为 $n$ 的约数, 则 $\frac{n}{p}$ 也是 $n$ 的约数, 所以我们只需用 $2\sim \sqrt{n}$ 的数来判定即可, 于是优化一下我们得到一个 $\mathcal{O}(\sqrt{n})$ 的算法.

1
bool isPrime(int n) {
2
  if (n == 1) return false;
3
  if (n == 2) return true;
4
  for (int i = 2; i * i <= n; ++i)
5
    if (n % i == 0) return false;
6
  return true;
7
}

整数惟一分解定理#

若整数 $n\ge2$ , 那么 $n$ 一定可以惟一地表示为若干素数的乘积, 形如

$n=p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k}(p_i为素数, r_i\ge0)$

1
vector <int> factor(int n) {
2
  vector <int> ret;
3
  for (int i = 2; i * i <= n; ++i)
4
    while (n % i == 0) {
5
      ret.push_back(i);
6
      n /= i;
7
    }
8
  if (n > 1) ret.push_back(n);
9
  return ret;
10
}

Eratosthenes 筛法#

Eratosthenes 筛法可以快速列举出给定范围内的所有素数.

一个合数一定可以写成 $p\cdot x$ 的形式, 其中 $p$ 为素数, $x$ 为整数, 因此对每一个 $p$ , 我们从小到大枚举 $x$ , 筛掉相应的 $p\cdot x$ 即可.

一点小改进: 当 $x<p$ 时, $p\cdot x$ 一定被 $x$ 的素因子筛过一遍, 所以我们枚举 $x$ 时从 $x=p$ 开始枚举.

时间复杂度: $\mathcal{O}(\frac{n}{2}+\frac{n}{3}+\frac{n}{5}+\cdots)=\mathcal{O}(n\log{\log{n}})$

1
bool isprime[N];
2

3
void Eratos(int n) {
4
  memset(isprime, 1, sizeof isprime);
5
  isprime[0] = isprime[1] = 0;
6
  for (int i = 2; i * i <= n; ++i)
7
    if (isprime[i]) {
8
      for (int j = i * i; j <= n; j += i)
9
        isprime[j] = 0;
10
    }
11
}

1
bool isprime[N];
2
int minfac[N];
3

4
void Eratos(int n) {
5
  memset(isprime, 1, sizeof isprime);
6
  isprime[0] = isprime[1] = 0;
7
  for (int i = 1; i <= n; ++i) minfac[i] = i;
8
  for (int i = 2; i * i <= n; ++i)
9
    if (isprime[i]) {
10
      for (int j = i * i; j <= n; j += i) {
11
        isprime[j] = 0;
12
        if (minfac[j] == j) minfac[j] = i;
13
      }
14
    }
15
}
16

17
vector <int> factor(int n) {
18
  vector <int> ret;
19
  while (n > 1) {
20
    ret.push_back(minfac[n]);
21
    n /= minfac[n];
22
  }
23
  return ret;
24
}

Euler 筛法#

在埃氏筛中, 30 这个数被 $p=2,3,5$ 分别筛了三次, 造成了重复, 如果我们能让每个数只被它最小的素因数筛, 就能做到 $\mathcal{O}(n)$ 的时间复杂度.

在 Euler 筛法中, 我们从 $2\sim n$ 枚举每一个数 $i$ , 若 $i$ 是素数, 则加入素数表中, 然后我们再从小到大枚举前面的素数 $prime[j]$ , 筛掉 $i\cdot prime[j]$ , 当 $prime[j]$ 是 $i$ 的一个素因数时, 那么后面再继续枚举到的素数一定不是所筛的数的最小素因数, 毕竟后面的素数一定大于当前的 $prime[j]$ , 所以这时可以终止筛选.

时间复杂度: $\mathcal{O}(n)$

1
int prime[N];
2
bool isprime[N];
3

4
void Euler(int n) {
5
  memset(isprime, 1, sizeof isprime);
6
  isprime[0] = isprime[1] = 0;
7
  for (int i = 2; i <= n; ++i) {
8
    if (isprime[i]) prime[++prime[0]] = i;
9
    for (int j = 1; j <= prime[0] && prime[j] * i <= n; ++j) {
10
      isprime[i * prime[j]] = 0;
11
      if (i % prime[j] == 0) break;
12
    }
13
  }
14
}

整数惟一分解定理的推论#

$N=p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k}$

1. $N$ 的正约数的个数为 $(r_1+1)(r_2+1)\cdots(r_k+1)=\prod_{i=1}^k(r_i+1)$
2. $N$ 的约数个数上界为 $\sqrt{N}$
3. $N$ 的所有正约数的和为 $(1+p_1+p_1^2+\cdots+p_1^{r_1})\cdots(1+p_k+\cdots+p_k^{r_k})=\prod_{i=1}^k(\sum_{j=0}^{r_i}p_i^j)$
4. 时间复杂度: $\mathcal{O}(\sqrt{N})$

高精度 $\gcd{(a, b)}$#

更相减损术适用于大整数下求 $\gcd(a, b)$

1. $a<b$ 时, $\gcd(a, b)=\gcd(b, a)$
2. $a=b$ 时, $\gcd(a, b)=a$
3. $a, b$ 同为偶数时, $\gcd(a, b)=2\gcd(\frac{a}{2}, \frac{b}{2})$
4. $a$ 为偶数, $b$ 为奇数时, $\gcd(a, b)=\gcd(\frac{a}{2}, b)$
5. $a$ 为奇数, $b$ 为偶数时, $\gcd(a, b)=\gcd(a, \frac{b}{2})$
6. $a, b$ 同为奇数时, $\gcd(a, b)=\gcd(b, a-b)$

错排问题#

1. 利用容斥原理求解

   令集合 $S$ 表示 $1,2, \cdots, n$ 的全排列, 则 $|S|=n!$

   设子集 $S_i$ 表示 $i$ 排在第 $i$ 位的排列, 则 $|S_i|=(n-1)!$

   同理, 设 $S_{i_1}\cap S_{i_2}\cap\cdots\cap S_{i_k}$ 表示 $i_1, i_2, \cdots, i_k$ 这 $k$ 个数排在相应位置的排列数, 则 $|S_{i_1}\cap S_{i_2}\cap\cdots\cap S_{i_k}|=(n-k)!$

   每个元素都不排在自己位置的排列数为 $D_n=|\overline{S_1}\cap\overline{S_2}\cap\cdots\cap\overline{S_n}|=|S|-|S_1\cup S_2\cup\cdots\cup S_n|$

   由容斥原理可得

   $D_n=n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots\pm\frac{1}{n!})$

2. 递推公式

   推导过程并不难想, 懒得写了, 直接上公式

   $D_n=(n-1)(D_{n-1}+D_{n-2})$

容斥原理求欧拉函数#

根据整数惟一分解定理, 将 $N$ 分解为

$N=p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k}$

设 $[1, n]$ 中 $p_i$ 的倍数的集合为 $A_i$ , 则 $|A_i|=\lfloor \frac{N}{p_i}\rfloor$

对于 $p_i\not=p_j$ , 有 $|A_i\cap A_j|=\lfloor\frac{N}{p_ip_j}\rfloor$

根据容斥原理,

$\begin{aligned}\varphi(N)&=|A|-|\overline{A_1}\cup\overline{A_2}\cup\cdots\cup\overline{A_k}| \\\ &=N-(\frac{N}{p_1}+\frac{N}{p_2}+\cdots+\frac{N}{p_k})+(\frac{N}{p_1p_2}+\cdots+\frac{N}{p_1p_k})-\cdots\pm\frac{N}{p_1p_2\cdots p_k} \\\ &=N(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_k})\end{aligned}$

素因数分解求欧拉函数的算法#

时间复杂度: $\mathcal{O}(\sqrt{n})$

1
int euler_phi(int n) {
2
  int ret = n;
3
  for (int i = 2; i * i <= n; ++i)
4
    if (n % i == 0) {
5
      ret = ret / i * (i - 1);//先除后乘可以一定程度上避免爆 int
6
      while (n % i == 0) n /= i;
7
    }
8
  if (n > 1) ret = ret / n * (n - 1);
9
  return ret;
10
}

埃氏筛法预处理欧拉函数值#

时间复杂度: $\mathcal{O}(n\log{\log{n}})$

1
int phi[N];
2

3
void euler_phi(int n) {
4
  for (int i = 2; i <= n; ++i) phi[i] = i;
5
  for (int i = 2; i * i <= n; ++i)
6
    if (phi[i] == i) {
7
      phi[i] = i - 1;
8
      for (int j = i; j <= n; j += i)//注意这里 j 的起点是 i 而不是 i * i
9
        phi[j] = phi[j] / i * (i - 1);
10
    }
11
}

欧拉函数的性质#

若 $a\bot b$ , 则 $\varphi(a)\varphi(b)=\varphi(ab)$ , 即欧拉函数具有积性函数的性质.

上式分别将 $a, b$ 用整数惟一分解定理表示, 然后带入欧拉函数计算式即可得到证明.

剩余系#

1. 剩余系指模正整数 $n$ 的余数所组成的集合.
2. 完全剩余系: 如果一个剩余系中包含了这个正整数 $n$ 所有可能的余数 ($0, 1, \cdots, n-1$) , 那么就称它为模 $n$ 的一个完全剩余系, 记作 $Z_n$ . 简化剩余系:完全剩余系中与 $n$ 互质的数的集合, 记作 $Z_n^*$ .
3. 同余等价类: $Z_n$ 里的每一个元素代表所有模 $n$ 意义下与它同余的整数, 我们把满足同余关系的所有整数看作一个同余等价类.
4. 在 $Z_n$ 中的四则运算结果全部都要在模 $n$ 意义下.

模运算#

1. 如果 $a\equiv b\pmod{m}$ 且有 $c\equiv d\pmod{m}$ , 那么:

   $a+c\equiv b+d\pmod{m}$

   $a-c\equiv b-d\pmod{m}$

   $a\times c\equiv b\times d\pmod{m}$

2. $(a+b)\bmod m=((a\bmod m)+(b\bmod m))\bmod m$

   $(a-b)\bmod m=((a\bmod m)-(b\bmod m)+m)\bmod m$

   $(a\times b)\bmod m=((a\bmod m)\times(b\bmod m))\bmod m$

快速幂#

右转 快速幂复习笔记

费马小定理#

若 $p$ 为素数, 且 $a\bot p$ , 则 $a^{p-1}\equiv 1\pmod{p}$ .

因为 $p$ 为素数, 则 $2, 3, \cdots, p-1$ 与 $p$ 互质, 且不存在两个数模 $p$ 同余.

又 $a\bot p$ , 所以 $a, 2a, 3a, \cdots, (p-1)a$ 与 $p$ 互质, 且不存在两个数模 $p$ 同余.

因此 $a\cdot 2a\cdot 3a\cdots(p-1)a=(p-1)!a^{p-1}$ 与 $p$ 互质, 且 $(p-1)!a^{p-1}\equiv (p-1)!\pmod{p}$

两边同时除以 $(p-1)!$ 得到 $a^{p-1}\equiv 1\pmod{p}$

1. 费马小定理的另一种形式: 若 $p$ 为素数, 则对任意正整数 $a$ 有 $a^p\equiv a\pmod{p}$.
2. 应用: $p$ 是素数, $a, p$ 互质, 则 $a^b\bmod{p}= a^{b\bmod (p-1)}\bmod{p}$ .

例题#

「POJ 3696」The Luckiest number

设 $n$ 个 8 连在一起的正整数为 $A_n$ , 则 $A_n=10A_{n-1}+8$ , 容易求得 $A_n=\frac{8}{9}(10^n-1)$ .

若 $L|A_n$ , 即 $L|\frac{8}{9}(10^n-1)$, 可以得到 $9L|8(10^n-1)$ , 令 $d=\gcd(9L, 8)$ , 则有 $\frac{9L}{d}|(10^n-1)$

于是 $10^n\equiv 1\pmod{\frac{9L}{d}}$

根据欧拉定理的引理, 只需求出 $\varphi(\frac{9L}{d})$ , 然后枚举它的约数, 一一验证后取最小的一个数即可.

时间复杂度: $\mathcal{O}(\sqrt{L}\log{L})$

裴蜀定理 ( Bézout 定理 )#

对任何整数 $a, b$ , 关于未知数 $x, y$ 的线性不定方程 ( 称为裴蜀等式 ) $ax+by=c$ 有整数解当且仅当 $c$ 为 $\gcd{(a, b)}$ 的倍数.

裴蜀等式有解时必有无穷多个解.

推论: $a, b$ 互素等价于 $ax+by=1$ 有整数解.

扩展欧几里得算法#

见 gcd & lcm 复习笔记

根据裴蜀定理, $ax+by=\gcd{(a, b)}$ 有无穷组解, 而扩展欧几里得算法求出来的只是其中一组特解 $(x_0, y_0)$ .

下面考虑求 $ax+by=c$ 的一般解.

首先设 $c=t\gcd(a, b)$ ( $t$ 为整数 ) , 则使用扩展欧几里得算法求出 $ax+by=\gcd{(a, b)}$ 的特解 $(x_0, y_0)$ 后, 容易得到 $ax+by=c$ 特解为 $(tx_0, ty_0)$ .

由于之后考虑的是 $ax+by=c$ , 所以后面用 $(x_0, y_0)$ 代替 $(tx_0, ty_0)$ .

将方程的所有解按照 $x$ 的大小排序, 则特解后的下一组解 $(x_1, y_1)$ 可以表示为 $(x_0+d_1, y_0+d_2)$ , 其中 $d_1$ 为满足条件的最小正整数.

带入方程后得到 $ad_1+bd_2=0$ , 变形后有 $-\dfrac{d_1}{d_2}=\dfrac{b}{a}=\dfrac{\frac{b}{\gcd{(a, b)}}}{\frac{a}{\gcd{(a, b)}}}$ .

因此方程的一般解可以表示为 $\left(x_0+k\dfrac{b}{\gcd{(a, b)}}, y_0-k\dfrac{a}{\gcd{(a, b)}}\right)(k\in \mathbf{Z})$ .

为什么这里要将 $\dfrac{b}{a}$ 再变形为 $\dfrac{\frac{b}{\gcd{(a, b)}}}{\frac{a}{\gcd{(a, b)}}}$ 呢?

因为 $\frac{b}{a}$ 不是最简分数, 这一步变形是化简 $\frac{b}{a}$ , 直接用 $(x_0+kb, y_0-ka)$ 来表示特解的话会漏掉一些情况, 如 $(x_0+\frac{b}{\gcd{(a, b)}}, y_0-\frac{a}{\gcd{(a, b)}})$ 就不能被 $(x_0+kb, y_0-ka)$ 表示.

模 $n$ 意义下乘法的逆#

如果在 $Z_n$ 中两元素 $a, b$ 满足 $a\cdot b=1$ , 那么我们就说 $a, b$ 互为模 $n$ 意义下乘法的逆元, 记作 $a=b^{-1}, b=a^{-1}$ .

逆元#

当 $a, m$ 互素的时候, 若 $ax\equiv 1\pmod{m}$ , 则称 $x$ 为 $a$ 关于模 $m$ 的逆元, 记作 $a^{-1}$ .

在 $[0, m)$ 的范围内, 逆元是唯一的.

求解逆元#

求解逆元等价于解方程 $ax+my=1$

直接使用扩展欧几里得算法即可.

1
inv[1] = 1;
2
for (int i = 2; i <= n; ++i)
3
  inv[i] = inv[p % i] * (p - p / i) % p;

例题#

「POJ 1845」Sumdiv

首先利用整数惟一分解定理将 $A$ 表示为 $A=p_1^{r_1}p_2^{r_2}\cdots p_n^{r_n}$ .

则 $A^B$ 约数和为

$(1+p_1+p_1^2+\cdots +p_1^{B\cdot r_1})(1+p_2+p_2^2+\cdots+p_2^{B\cdot r_2})\cdots(1+p_n+p_n^2+\cdots+p_n^{B\cdot r_n})$

可以发现, 每一个括号里都是一个等比数列求和, 以 $p_i$ 为例, 它的和可以写成 $\dfrac{p_i^{B\cdot r_i+1}-1}{p_i-1}$ , 然后我们可以利用快速幂求解分子 $p_i^{B\cdot r_i+1}\bmod{9901}$ , 这时若 $p_i-1>(p_i^{B\cdot r_i+1}-1)\bmod{9901}$ , 我们会得到 $0$ , 这显然是错的, 而模数 $9901$ 正好为素数, 因此考虑用 $p_i-1$ 的逆元与分子的结果相乘来代替除法.

当 $p_i-1$ 为 $9901$ 的倍数时不存在逆元, 这时我们可以发现 $p_i\equiv 1\pmod{9901}$ , 因此 $1, p_i, p_i^2, \cdots, p_i^{B\cdot r_i+1}\equiv 1\pmod{9901}$ , 所以 $1+p_i+p_i^2+\cdots+p_i^{B\cdot r_i}\equiv B\cdot r_i+1\pmod{9901}$ .

例题#

线性组合

对应整数数列 $A_1, A_2, \cdots, A_n$ 是否存在 $X_1, X_2, \cdots, X_n$ ， 使得 $A_1X_1+A_2X_2+\cdots+A_nX_n=C$ ，其中 $\gcd{(A_1, A_2, \cdots, A_n)}\mid C(n\ge2)$ 。如有，请找出一组整数解 $(x_1, x_2, x_3, x_4)$ 满足 $12x_1+24x_2+18x_3+15x_4=3$ .

题中的方程是 n 元形式的扩展欧几里得方程，我们尝试将 n 元逐步降为二元得到最终解。

设 $d=\gcd{(A_1, A_2, \cdots, A_n)}$ ，令 $C'=\dfrac{C}{d},A_i'=\dfrac{A_i}{d}(i=1, 2, \cdots, n)$ ，首先将方程变形为 $A_1'X_1+A_2'X_2+\cdots+A_n'X_n=C'$ ，此时满足 $\gcd{(A_1', A_2', \cdots, A_n', C')}=1$ 。

然后我们考虑求解方程 $A_1'X_1+\gcd(A_2', A_3', \cdots, A_n')Y_1=C'$ ，利用扩展欧几里得方法求得特解 $X_1,Y_1$ ，由于题中仅要求得到一组解，因此我们只取特解即可，然后再以同样的方法求解 $A_2'X_2+A_3'X_3+\cdots+A_n'X_n=\gcd(A_2', A_3', \cdots, A_n')Y_1$ 便可以实现逐渐降元了。

线性同余方程组（模互素）#

考虑形如 $x\equiv a_i\pmod{m_i}$ 的若干个线性同余方程联合得到的方程组，例如

一种可行的解法是令 $x=3y+2$ ，然后将方程 $(2)$ 改写成 $y\equiv 2\pmod{5}$ ，接着再令 $y=5z+2$ 代入方程 $(3)$ 得到 $z\equiv 4\pmod{7}$ ，再令 $z=7k+4$ ，最后我们可以得到解 $x\equiv68\pmod{105}$ 。

1
//China Remainer Theorem
2
int CRT(const int a[], const int m[], int n) {
3
  int M = 1, ret = 0;
4
  for (int i = 1; i <= n; ++i) M *= m[i];
5
  for (int i = 1; i <= n; ++i) {
6
    int ti = getinv(m[i], a[i]), Mi = M / m[i];
7
    ret = (ret + a[i] * ti * Mi % M) % M;
8
  }
9
  return ret;
10
}
11

12
//利用 exgcd 求逆元
13
int getinv(int a, int b) {
14
  int x, y;
15
  exgcd(a, b, x, y);
16
  return x;
17
}

线性同余方程组（模不互素）#

对于模不互素的线性同余方程组

考虑求解方程数量为 2 的情形，当方程数量大于 2 时迭代求解。