数论基础

位运算

位运算是直接对整数的二进制位进行操作。由于计算机内部使用二进制存储整数，因此位运算通常具有较高的执行效率。

基本运算

设两个二进制数为：

$$a=1100_2,\qquad b=1010_2$$

按位与 &

只有对应的两个二进制位都为 $1$，结果位才为 $1$。

$$1100_2\& \ 1010_2=1000_2$$

常用于判断某一位是否为 $1$。

按位或 |

只要对应的两个二进制位中至少有一个为 $1$，结果位就为 $1$。

$$1100_2\ |\ 1010_2=1110_2$$

常用于将某一位设置为 $1$。

按位异或 ^

对应的两个二进制位不同时，结果位为 $1$；相同时，结果位为 $0$。

$$1100_2\ \hat{}\ 1010_2=0110_2$$

异或运算具有以下性质：

$$a\oplus 0=a$$ $$a\oplus a=0$$ $$a\oplus b=b\oplus a$$ $$(a\oplus b)\oplus c=a\oplus(b\oplus c)$$

因此，一个数连续异或两次同一个数后保持不变：

$$a\oplus b\oplus b=a$$

按位取反 ~

将整数的每一个二进制位取反，即 $0$ 变为 $1$，$1$ 变为 $0$。

在补码表示下，有：

$$\sim x=-x-1$$

左移 <<

将二进制位整体向左移动，右侧补 $0$。

在不发生溢出的情况下：

$$x\ll k=x\times 2^k$$

例如：

$$3\ll 2=12$$

因为：

$$0011_2\ll 2=1100_2$$

右移 >>

将二进制位整体向右移动。

对于非负整数：

$$x\gg k=\left\lfloor\frac{x}{2^k}\right\rfloor$$

例如：

$$13\gg 2=3$$

因为：

$$1101_2\gg 2=0011_2$$

常用操作

以下操作中的第 $k$ 位从第 $0$ 位开始编号。

判断第 $k$ 位是否为 $1$

if (x & (1LL << k)) {
    // x 的第 k 位为 1
}

也可以写成：

int bit = (x >> k) & 1;

将第 $k$ 位设置为 $1$

x |= 1LL << k;

将第 $k$ 位设置为 $0$

x &= ~(1LL << k);

将第 $k$ 位取反

x ^= 1LL << k;

获取最低位的 $1$

lowbit(x) 表示 $x$ 的二进制表示中最低位的 $1$ 所对应的数值。

int lowbit(int x) {
    return x & -x;
}

例如：

$$12=1100_2$$

最低位的 $1$ 对应的数为：

$$0100_2=4$$

因此：

$$\operatorname{lowbit}(12)=4$$

删除最低位的 $1$

x &= x - 1;

例如：

$$12=1100_2$$

执行一次后：

$$1100_2\&\ 1011_2=1000_2$$

每执行一次 x &= x - 1，就会删除一个二进制位中的 $1$。

因此可以统计一个整数二进制表示中 $1$ 的个数：

int countOne(int x) {
    int cnt = 0;
    while (x) {
        x &= x - 1;
        ++cnt;
    }
    return cnt;
}

时间复杂度为：

$$O(k)$$

其中 $k$ 为 $x$ 的二进制表示中 $1$ 的个数。

判断一个正整数是否为 $2$ 的幂

若正整数 $x$ 是 $2$ 的幂，则它的二进制表示中只有一个 $1$。

因此：

bool isP(int x) {
    return x > 0 && (x & (x - 1)) == 0;
}

A 找筷子

B 高低位交换

快速幂

任意非负整数 $b$ 都可以表示成若干个 $2$ 的幂之和。

例如：

$$13=8+4+1=2^3+2^2+2^0$$

long long Pow(long long a, long long b) {
    long long res = 1;

    while (b) {
        if (b & 1)
            res *= a;
        a *= a;
        b >>= 1;
    }

    return res;
}

C 快速幂

素数

• 整数集合：$\mathbb{Z}=\{\ldots,-2,-1,0,1,2,\ldots\}$

• 自然数集合：$\mathbb{N}=\{0,1,2,\ldots\}$

• 整除：若 $a=bk$，其中 $a,b,k$ 都是整数，则 $b$ 整除 $a$，记作 $b\mid a$，否则记作 $b\nmid a$。

• 约数：如 $b\mid a$ 且 $b\ge 0$，则称 $b$ 是 $a$ 的约数（因数），$a$ 是 $b$ 的倍数。

• $1$ 整除任何数，任何数都整除 $0$。

• 若 $a\mid b,\ a\mid c$，则 $a\mid(b+c),\ a\mid(b-c)$。

• 若 $a\mid b$，则对任意整数 $c$，$a\mid(bc)$。

• 传递性：若 $a\mid b,\ b\mid c$，则 $a\mid c$。

• 因子：正整数 $a$ 的平凡约数为 $1$ 和 $a$ 本身，$a$ 的非平凡约数称为 $a$ 的因子。如 $20$ 的因子有 $2、4、5、10$。

• 素数：$a>1$ 且只能被平凡约数整除的数。

• 合数：$a>1$ 且不是素数的数称为合数。

• 其他整数（$0,1$，负整数）既不是素数也不是合数。

• 素数有无穷多个，但分布比较稀疏，不大于 $n$ 的素数约有 $\dfrac{n}{\ln n}$ 个。

若 $n$ 是一个合数，则 $n$ 至少有 $1$ 个素因子。因此其中最小的素因子一定不大于 $\sqrt{n}$。

如果 $n$ 是合数，则一定可以分解为 $a\times b$ 的形式，其中 $a\le b,\ a\ne 1,\ b\ne n$，如：

$$18=2\times 9,\qquad 18=3\times 6$$

因 $a\times a\le a\times b=n$，则可得：

$$a\le\sqrt{n}$$

可得判断依据：如果 $2\sim\sqrt{n}$ 中有 $n$ 的约数，则 $n$ 是合数，否则 $n$ 是素数。

bool isPrime(int n) {
    if (n == 1) return false;
    else {
        for (int i = 2; i * i <= n; i++)
            if (n % i == 0) return false;
        return true;
    }
}

素因数分解

D 因数分解

素数筛

埃氏筛

每个合数 $a$ 一定可以写成 $p\times x$ 的形式，其中 $p$ 是素数，$x$ 是倍数（$x\ne 1$）。对于每一个 $1\sim n$ 内的素数 $p$，枚举倍数 $x$，把 $p\times x$ 标记为合数，这就是埃氏筛法。

筛选时做一个改进：对于素数 $p$，只筛倍数 $x\ge p$ 的数，因为如果 $x<p$，则 $x$ 中一定有比 $p$ 小的素因子，$p\times x$ 会在前面的筛选过程中被筛出。

因此只需考虑 $2\sim\sqrt{n}$ 范围的素数。

时间复杂度：

$$O\left(\frac{n}{2}+\frac{n}{3}+\frac{n}{5}+\cdots\right) =O(n\log\log n)$$

#define maxn 1000000

bool isPrime[maxn + 1]; /* isPrime[i] 为 true 表示 i 为素数 */

void eratos(int n) {
    int i, j;
    isPrime[0] = isPrime[1] = false;

    for (i = 2; i <= n; ++i)
        isPrime[i] = true;

    for (i = 2; i * i <= n; ++i)
        if (isPrime[i]) {
            for (j = i * i; j <= n; j += i)
                isPrime[j] = false;
        }
}

由于数据范围很大，无法生成 $[1,R]$ 中的所有素数。

使用筛法求出 $[2,\sqrt{R}]$ 之间的所有素数，对于每个素数 $p$，把 $[L,R]$ 中能被 $p$ 整除的数标记，即标记：

$$i\times p \qquad \left(\left\lceil\frac{L}{p}\right\rceil \le i\le \left\lfloor\frac{R}{p}\right\rfloor\right)$$

为合数。

将筛出的素数进行相邻两两比较，找出差最大的即可。

欧拉筛法（线性筛）

埃氏筛法中，以 $n=50$ 为例，$30$ 这个数被筛了 $3$ 次，分别是：

$$2\times 15\quad(p=2)$$ $$3\times 10\quad(p=3)$$ $$5\times 10\quad(p=5)$$

如何用 $O(n)$ 求 $1\sim n$ 的素数？

如果每个合数只被它的最小素因数筛除，那么每个数最多只被筛一次。

$i=$	素数表	筛除的数	$i=$	素数表	筛除的数
2	$\{2\}$	$\{4\}$	13	$\{2,3,5,7,11,13\}$	$\{26,39\}$
3	$\{2,3\}$	$\{6,9\}$	14		$\{28\}$
4		$\{8\}$	15		$\{30,45\}$
5	$\{2,3,5\}$	$\{10,15,25\}$	16		$\{32\}$
6		$\{12\}$	17	$\{2,3,5,7,11,13,17\}$	$\{34\}$
7	$\{2,3,5,7\}$	$\{14,21,35,49\}$	18		$\{36\}$
8		$\{16\}$	19	$\{2,3,5,7,11,13,17,19\}$	$\{38\}$
9		$\{18,27\}$	20		$\{20\}$
10		$\{20\}$	21		$\{42\}$
11	$\{2,3,5,7,11\}$	$\{22,33\}$	22		$\{44\}$
12		$\{24\}$	...	...

枚举 $2\sim n$ 中的每一个数 $i$：

• 如果 $i$ 是素数，则保存到素数表中；
• 利用 $i$ 和素数表中的素数 $\operatorname{prime}[j]$ 去筛除 $i\times\operatorname{prime}[j]$。为了确保 $i\times\operatorname{prime}[j]$ 只被素数 $\operatorname{prime}[j]$ 筛除过这一次，要确保 $\operatorname{prime}[j]$ 是 $i\times\operatorname{prime}[j]$ 中最小的素因子，即 $i$ 中不能有比 $\operatorname{prime}[j]$ 还要小的素因子。

E 线性筛素数

约数

若整数 $N\ge 2$，那么：

$$N=p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k} \qquad (p_i\text{ 为素数},\ r_i\ge 0)$$

$N$ 的正约数集合为：

$$\left\{ p_1^{b_1}p_2^{b_2}\cdots p_k^{b_k} \right\} \qquad (0\le b_i\le r_i)$$

$N$ 的正约数个数为：

$$(r_1+1)(r_2+1)\cdots(r_k+1)=\prod_{i=1}^{k}(r_i+1)$$

除了完全平方数，约数总是成对出现的，即 $d\le\sqrt{N}$ 和 $\dfrac{N}{d}\le\sqrt{N}$ 都是 $N$ 的约数。

$N$ 的约数个数上界为 $2\sqrt{N}$，时间复杂度为 $O(\sqrt{N})$。

$N$ 的所有正约数的和为：

$$(1+p_1+p_1^2+\cdots+p_1^{r_1}) \cdots (1+p_k+p_k^2+\cdots+p_k^{r_k}) = \prod_{i=1}^{k} \left( \sum_{j=0}^{r_i}p_i^j \right)$$

F 反素数

对于任何正整数 $x$，其约数的个数计作 $g(x)$。例如：

$$g(1)=1,\qquad g(6)=4$$

如果某个正整数 $x$ 满足：对于任意的 $0<i<x$，都有 $g(x)>g(i)$，那么称 $x$ 为反素数。例如 $1,2,4,6$ 都是反素数。

现在给定一个数 $N$（$1\le N\le 2\times 10^9$），求出不超过 $N$ 的最大的反素数。

最大公约数

设 $a,b$ 是不都为 $0$ 的整数，$c$ 为满足 $c\mid a$ 且 $c\mid b$ 的最大整数，则称 $c$ 是 $a,b$ 的最大公约数，记为 $\gcd(a,b)$ 或 $(a,b)$。

最大公约数有如下性质：

$$\gcd(a,b)=\gcd(b,a)$$ $$\gcd(a,b)=\gcd(-a,b)$$ $$\gcd(a,b)=\gcd(|a|,|b|)$$

若 $d\mid a$ 且 $d\mid b$，则：

$$d\mid\gcd(a,b)$$ $$\gcd(a,0)=a$$ $$\gcd(a,ka)=a$$ $$\gcd(an,bn)=n\gcd(a,b)$$ $$\gcd(a,b)=\gcd(a,ka+b)$$

计算 $\gcd(a,b)$：枚举法

从 $\min(a,b)$ 到 $1$ 枚举 $x$，并判断 $x$ 是否能同时整除 $a$ 和 $b$。

如果可以，则输出 $x$ 并退出循环。

时间复杂度为：

$$O(\min(a,b))$$

计算 $\gcd(a,b)$：欧几里得算法

两个整数 $a,b$（$a\ge b$）的公约数集合与 $a-b$ 和 $b$ 的公约数集合相同，可得：

$$\gcd(a,b)=\gcd(b,a\bmod b)$$

又称“辗转相除法”。

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

根据 $(a,b)\Rightarrow(b,a\bmod b)$，设 $a>b$：

1. 当 $a\ge 2b$ 时，$b\le\dfrac{a}{2}$，$b$ 的规模至少缩小一半；
2. 当 $a<2b$ 时，$a\bmod b<\dfrac{a}{2}$，余数的规模至少缩小一半。

所以时间复杂度为：

$$O(\log(a+b))$$

G 兔八哥与猎人

H 又是毕业季I

最小公倍数

两个数 $a_1,a_2$ 的最小公倍数：

$$\operatorname{lcm}(a_1,a_2) = \frac{a_1a_2}{\gcd(a_1,a_2)}$$$$\operatorname{lcm}(a_1,a_2,a_3) = \operatorname{lcm}(\operatorname{lcm}(a_1,a_2),a_3)$$

以此类推，可以先求 $a_1,a_2$ 的最小公倍数 $b_1$，再求 $b_1$ 与 $a_3$ 的最小公倍数 $b_2$，再求 $b_2$ 与 $a_4$ 的最小公倍数 $b_3\ldots$

容斥

现在有：

$$S=\{1,2,3,\ldots,600\}$$

求其中可被 $2,3,5$ 整除的数的数目。

令 $A,B,C$ 分别表示 $S$ 中被 $2,3,5$ 整除的数的集合。可得：

$$|A|=\left\lfloor\frac{600}{2}\right\rfloor=300,\qquad |B|=\left\lfloor\frac{600}{3}\right\rfloor=200,\qquad |C|=\left\lfloor\frac{600}{5}\right\rfloor=120$$

显然 $A,B$ 集合中一定有相同的元素，比如 $6,12,\ldots$，可继续求 $A,B,C$ 两两交集的情况：

$$|A\cap B| = \left\lfloor\frac{600}{2\times 3}\right\rfloor =100$$$$|A\cap C| = \left\lfloor\frac{600}{2\times 5}\right\rfloor =60$$$$|B\cap C| = \left\lfloor\frac{600}{3\times 5}\right\rfloor =40$$

最后求 $A,B,C$ 三个集合的交集情况：

$$|A\cap B\cap C| = \left\lfloor\frac{600}{2\times 3\times 5}\right\rfloor =20$$

具有性质 $A$ 或者 $B$ 的元素个数，等于具有性质 $A$ 的元素个数与具有性质 $B$ 的元素个数的和，减去同时具有性质 $A$ 和 $B$ 的元素的个数，使得计算的结果既无遗漏又无重复。这就是容斥原理，一般表示如下：

$$\left|\bigcup_{i=1}^{m}A_i\right| = \sum_{1\le i\le m}|A_i| - \sum_{1\le i<j\le m}|A_i\cap A_j| + \sum_{1\le i<j<k\le m}|A_i\cap A_j\cap A_k| -\cdots + (-1)^{m+1}|A_1\cap A_2\cap\cdots\cap A_m|$$

J 信封问题

取模

如果 $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$$

以下用“$\%\,m$”代表“$\pmod m$”：

$$(a+b)\%m=((a\%m)+(b\%m))\%m$$ $$(a-b)\%m=((a\%m)-(b\%m)+m)\%m$$ $$(a\times b)\%m=((a\%m)\times(b\%m))\%m$$

逆元

对于一个模数 $p$ 和一个除数 $x$，往往能找到一个特殊的数。乘上这个特殊的数，就可以起到除法的效果。这个特殊的数，称为“逆元”。

$4$ 是 $3$ 在模 $11$ 意义下的逆元。

费马小定理

若 $p$ 为素数，且 $a$ 和 $p$ 互素，则可以得到：

$$a^{p-1}\equiv 1\pmod p$$

证明：

$p-1$ 个整数 $a,2a,3a,\ldots,(p-1)a$ 中没有一个是 $p$ 的倍数，而且没有任意两个模 $p$ 同余。

所以这 $p-1$ 个数对模 $p$ 的同余是 $1,2,3,\ldots,(p-1)$ 的排列。

可得：

$$a\cdot 2a\cdot 3a\cdots(p-1)a \equiv 1\cdot 2\cdot 3\cdots(p-1) \pmod p$$

可化简为：

$$a^{p-1}(p-1)!\equiv(p-1)!\pmod p$$

即：

$$a^{p-1}\equiv 1\pmod p$$

得证。

一般情况下，在 $p$ 是素数的情况下，对任意整数 $a$ 都有：

$$a^p\equiv a\pmod p$$

费马小定理应用：$p$ 是素数，$a,p$ 互素，则：

$$a^b\bmod p = a^{\,b\bmod(p-1)}\bmod p$$

如 $p=5,\ a=3$：

$$3^4=81\equiv 1\pmod 5$$

又如：

$$3^{2046} = 3^{4\times 511+2} \equiv 3^2 \pmod 5 \equiv 4 \pmod 5$$

K 【模板】模意义下的乘法逆元

练习

CF58B Coins

CF679A Bear and Prime 100

[POJ 2689] Prime Distance