本文经 @sLMxf 转载：
整除和余数
- 以下 $x、y、a$ 均为整数。
- 存在整数 $k$，使得 $x = ky$，则有 $y|x$（ $y$ 整除 $x$ ），若 $y>0$ 则称 $x$ 是 $y$ 的倍数，$y$ 是 $x$ 的因数。
- 如果 $x = ky + a$，则称 $a$ 为 $x/y$ 的余数，写作 $a = x % y$，当 $a = 0$ 当且仅当 $y|x$。
同余
- 如果 $x % z = y % z$ ，则我们称 $x$ 和 $y$ 对 $z$ 同余，记作 $x \equiv y \pmod z$。
- 如果 $(x − y)$ 是 $z$ 的倍数，那么 $x$ 和 $y$ 对 $z$ 同余。
证明：记 $x = cz + a,y = dz + b（0 \le a,b < z) $ 则 $x − y = (c − d)z + a − b$，由于 $(x − y)$ 是 $z$ 的倍数，所以 $(a − b)|z$，而 $0 \le a,b < z$，故易得 $a = b$，所以同余。 - 如果且 $a \equiv b \pmod m,c \equiv d \pmod m$ ，则 $a\pm c \equiv b\pm d \pmod z$，证明雷同上面。
- 乘号同理，但是除法不行。
- 如果 $a \equiv b \pmod m$，则 $a^n \equiv b^n\pmod m$。
取余运算
- $(a + b) % m = (a % m + b % m) % m$
- $(a − b) % m = (a % m − b % m \color{red}{+ m}\color{black}) % m$
- $(a \times b) % m = (a % m \times b % m) % m$
- $a^b % m = (a % m)^b % m$
- 这些等式可以用在需要取模，且数字会经过多次运算的题目中，防止中间变量超出数据范围。
质数
- 只能被 $1$ 和自己整除的数,称为质数
- 当 $N$ 充分大时，$1$ ~ $N$ 范围内的质数个数约为 $N/\log N$。
- 在某个正整数 $N$ 附近找质数，能够在 $\log N$ 期望时间内发现一个质数。
- 如何判断一个整数 $n$ 是否为质数：$2$ 到 $\sqrt{n}$ 试除，发现约数则不是质数，复杂度 $O(\sqrt{n})$
- $a$ 和 $n/a$ 中至少有 $1$ 个数不超过 $\sqrt{n}$，完全平方数的情况 $2$ 个数都等于 $\sqrt{n}$。
筛法（埃式筛）
- 在学数组的时候，我们学过一个判断 $1$ ~ $n$ 是否为质数的方法：从小到大，依次将每个质数的倍数删去（若遍历到一个数时，其没有被删去，则可知这个数是质数），最终留下的全是质数。
1 | f[1]=false; |
- $j$ 从 $i\times i$ 开始是因为 $2\times i$、$3\times i$ 等数字在 $i=2,i=3$ 的时候已经被枚举过了。
- 时间复杂度 $O(n\log\log n)$。
筛法（线性筛）
- 数字 $30$ 还是被筛了多次（$3\times 10、2\times15、5\times 6$）。如果能保证每个合数都只被它的最小质因数筛掉就好了。
比如 $2$ 筛掉 $4、6、8、10、12\cdots$
比如 $3$ 筛掉 $9、15、21\cdots$
比如 $5$ 筛掉 $25、35、55\cdots$ - 我们记求解到 $i$ 的质数数组为 $p$，则对于每个数字 $i$，我们希望 $i\times p_1、i\times p_2$ 等数字都被筛掉。这样一定是能筛干净的，因为合数 $a=$ 某个质数 $b\times$ 另一个数 $c$，我们一定能在枚举到每个合数前，枚举到比它小的 $c$，这样当 $p_j=b$ 时，$a$ 就被干掉了。
- 每个合数还是没有只被它的最小质因数筛。
- 如 $60$，被 $3\times 20$干掉一次，被 $15\times 4$干掉一次。
1 | f[1]=false; |
- 内层循环加上一句
if(i%p[j]==0)break;即可。为什么？ - 此时，比
p[j]小的质数p[k]不满足p[k]$|i$，且 $i$ 的所有质因数肯定都比p[j]大，因为如果有小的那 $j$ 早就被停在前面了。故被筛掉的 $i\times$p[k]的最小质因数肯定是p[k]。 - 同理可证，设有比
p[j]大的质数p[l]，则删p[l]$\times i$ 一定会出现重复，因为假设p[l]$\times i /$p[j]是 $x$，当 $i$ 枚举到 $x$ 时候，$x\times$p[j]又会把这个数字筛一次。 - 时间复杂度 $O(n)$。
1 | f[1]=false; |
唯一分解定理
- 任何大于1的正整数n仅能以唯一方式分解为有限质数的乘积：
- $n = p_1^{e_1} \times p_2^{e_2} \cdots \times p_t^{e_t}$
- 其中 $p_i$ 是质数，$e_i$ 是正整数，且 $i$ 和 $\sum e_i$都是 $\log n$ 数量级别的。
- 根据乘法定理易得 $n$ 的因数个数为 $(e_1+1)\times (e_2+1)\times\cdots\times(e_t+1)$。
- 还能求出 $n$ 的因数和为 $(p_1^{e_1}+p_1^{e_1-1}+p_1^{e_1-2}+\cdots +p_1)(p_2^{e_2}+p_2^{e_2-1}+p_2^{e_2-2}+\cdots +p_2)\cdots (p_n^{e_n}+p_n^{e_n-1}+p_n^{e_n-2}+\cdots +p_n)$。
- 算术基本定理是一条非常基本和重要的定理，它把对自然数的研究转化为对其最基本的元素——质数的研究。
质因数分解
- $2$ 到 $\sqrt{n}$ 都试一下，如果能除的尽 $n$ 就用
while除，要把次数记下来。 - 最后剩下的数字如果步数 $1$ ，一定是最大的质因数。
gcd 和 lcm
- 若 $m|x$ 且 $m|y$ ，称为 $m$ 为 $x$ 和 $y$ 的公因数。最大的 $m$ 叫最大公因数 $(gcd)$。
- 若 $x|n$ 且 $y|n$，称为 $n$ 为 $x$ 和 $y$ 的公倍数。最小的 $n$ 叫最小公倍数 $(lcm)$ 。
- 设 $d = \gcd(x,y)$，那么 $d$ 的唯一分解中任意质数的指数 $e_i$ 为 $x,y$ 的唯一分解中此质数指数的 $\min$。
- 设 $e = lcm(x,y)$，那么 $e$ 的唯一分解中任意质数的指数 $e_i$为 $x,y$ 的唯一分解中此质数指数的 $\max$。
- 比如 $\gcd(240,180)=60$，分解质因数如下，发现 $60$ 的质因数中 $2$ 和$3$的指数取得是上面两个数分解 $2$ 和 $3$ 的指数的最小值
- $180 = 2^2 \times 3^2 \times 5^1$
- $240 = 2^4 \times 3^1 \times 5^1$
- $60 = 2^2 \times 3^1 \times 5^1$
- $lcm$ 则是取最大值，易得 $\gcd(x,y) \times lcm(x,y) = x \times y$
位运算
- $&$ 运算：二进制下进行二元运算，每一位全 $1$ 则 $1$ ，反之为 $0$。性质：$a&b\le \min(a,b)$.
- $|$ 运算：二进制下进行二元运算，每一位有 $1$ 则1，反之为 $0$。性质：$a|b\ge \max(a,b)$.
- ^ 运算：二进制下进行二元运算，每一位不同则 $1$，反之为 $0$。性质是自己就是自己的逆运算。
- $\sim$ 运算：一元运算符（和符号一样），让二进制下的每一位都取反（包括符号位）。
- $<<$运算：进制下把每一位向左平移，低位用 $0$ 补足。
- $1<<n$ 等价于 $2n$，$x<<n$ 等价于 $x \times 2n$
- $>>$运算：进制下把每一位向右平移，低位越界则舍弃。
- $n>>1=\lfloor\frac{n}{2}\rfloor$
- 注意位运算$\color{red}优先级很低$，搞不清就打括号！
一些操作
- $lowbit(n)$ 表示表示二进制下 $n$ 的最低的一个 $1$ 它后面的 $0$ 组成的数.
- $lowbit(n)=(n)\text{ and }(-n)$，原理自己想。
- $popcount(n)$ 表示二进制 $n$ 有多少位是 $1$，原理自己想。
1 | int ans=0; |
