数论基础技巧

「输了三把」
「我赢了三把」
「你们两个为什么输赢还不一样」
「因为 GCD，$a$ 和 $b$ 两个正整数，可以任意加减，能得到的最小正整数是 $\gcd(a,b)$」

【暴力循环】 下面这个表保证很多东西不太大，比如：

• 素数距离 ：对于 $n>3$，$n<p<2n-2$ 中至少有一个 $p$ 是素数；$10^{9}$ 范围内最大素数距离为 300。给定 $l,r$，找到 $l \leqslant A \leqslant B \leqslant r$ 且 $(A,B) = 1$，最大化 $\left\vert A-B \right\vert$，直接写两重循环，$10^{18}$ 的数据也跑得飞快。
• 素因子个数 ：$c_{i,j}=\gcd(i,a)+\gcd(j,b)$，求从左上走到右下的最小代价。设 $A$ 是最大的与 $a$ 互素的数，$B$ 是最大的与 $b$ 互素的数，从左上到点 $(A,B)$ 的最小额外代价是 $(A-1)+(B-1)$，而且不可能存在超过连续 26 个数字与 $a$ 不互素（因为连续 $p$ 个数必有一个 $p$ 的倍数，查表知 $\omega(n)=9$ 时 $n$ 已经远远超过 1e6），即 $n-A<25$，剩下 $25\times 25$ 暴力 DP 即可。
• 前缀 GCD 数量 ：设 $g_i$ 为 $a_i$ 的前 / 后缀 GCD，则 $g_i$ 的取值只有 $O(\log V)$ 种。
• 不超过 $n$ 的所有数的因子总数，lcm 不超过 $n$ 的无序对数，都是 $n\log n$ 量级。
• 递推数列具有模周期性，而且对于斐波那契数列，这个周期不会超过 $6\times$ 模数。
• 找出所有正整数 $k$ 使得 $\lbrace A_{i}\text{mod}k \rbrace$ 恰好有 $C$ 种数值不同的数且每种数的出现次数相等。枚举 $k$，检查是否合法。考察 $k$ 的上限，枚举到 $k$ 作为模数时，实际上把 $0\sim V$ 划分成了 $\lceil \frac{V}{k} \rceil$ 个分区：$[0, k), [k, 2k),\dots, [\lfloor \frac V k \rfloor k, V)$，按要求每个分区包含的数字不能超过 $C$ 种，即整个 $\lbrace A_{i} \rbrace$ 最多只能有 $C \lceil \frac{V}{k} \rceil$ 种数字，因此 $C \lceil \frac{V}{k} \rceil \geqslant |A| \implies k \leqslant \frac{V}{\lceil \frac{|A|}{C} \rceil - 1}$。总的时间复杂度便是严格的 $\mathcal{O}(N\log N + VC)$ 。

【枚举约数】 数据范围 $10^{4}$，某中间答案是一个数 $x$ 的约数，枚举这个中间答案以计算最终答案， 特判全部相等（即特判 0 的约数，此时 $x=0$ 什么也没有枚举），比如：

• 模 $k$ 下，$a$ 与 $b$ 的不进位加法等于 $c$，找出一个 $k$，或报告不存在。发现 $k\mid a+b-c$。
• $b_i = a_i \bmod k$，给定 $a$ 和打乱的 $b$，找出 $k$。发现 $k\mid\operatorname{sum}(a)-\operatorname{sum}(b)$。
• 给定序列及 $k$，找出所有满足 $1 \leqslant x \leqslant k$ 的整数 $x$，使得序列每个数加上 $x$ 后，所有子区间中都存在一个数整除这个区间的每个数。发现序列最小值 $a_{j}$ 满足 $(a_{j}+x)\mid \gcd(a_{i+1}-a_{i},\dots)$。
• 给定 $n$，求满足 $1 \leqslant m \leqslant n$ 且 $n\bmod m$ 等于 $m$ 的数码和 $S(m)$ 的 $m$ 的数量。发现 $S(m)$ 不多，而且 $m\mid n-S(m)$。

【GCD 性质】 GCD (Greatest Common Divisor) 比较重要的性质：

• $(a,b)=(a,a-b)$，把一群数的 GCD 转化为差分 GCD，适用于整体加减。
• 四个经典的代数性质：设 $a \neq b$，$\gcd(a,b) \leqslant \min\lbrace a,b \rbrace,\dfrac{\max\lbrace a,b \rbrace}{2}, \dfrac{a+b}{3},|a-b|$，用于估计 GCD 上界。
• 裴蜀定理 Bézout’s Lemma：$\min ax+by=\gcd(a,b)$。
• 经典数论技巧，设 $d=(a, b), a = a_{1} d, b = b_{1} d$。

$n$	$\log_{10} n$	$n!$	$C(n, n/2)$	$\text{lcm}(1 \dots n)$
2	0.30102999	2	2	2
3	0.47712125	6	3	6
4	0.60205999	24	6	12
5	0.69897000	120	10	60
6	0.77815125	720	20	60
7	0.84509804	5040	35	420
8	0.90308998	40320	70	840
9	0.95424251	362880	126	2520
10	1	3628800	252	2520
11	1.04139269	39916800	462	27720
12	1.07918125	479001600	924	27720
15	1.17609126	$1.31\text{e}12$	6435	360360
20	1.30103000	$2.43\text{e}18$	184756	232792560
25	1.39794001	$1.55\text{e}25$	5200300	26771144400
30	1.47712125	$2.65\text{e}32$	155117520	$1.444\text{e}14$

$n \le$	$\max\{\omega(n)\}$	$\max\{d(n)\}$	$\pi(n)$
10	2	4	4
100	3	12	25
$10^3$	4	32	168
$10^4$	5	64	1229
$10^5$	6	128	9592
$10^6$	7	240	78498
$10^7$	8	448	664579
$10^8$	8	768	5761455
$10^9$	9	1344	$5.08\text{e}7$
$10^{10}$	10	2304	$4.55\text{e}8$
$10^{11}$	10	4032	$4.12\text{e}9$
$10^{12}$	11	6720	$3.76\text{e}10$
$10^{13}$	12	10752	—
$10^{14}$	12	17280	—
$10^{15}$	13	26880	—
$10^{16}$	13	41472	—
$10^{17}$	14	64512	—
$10^{18}$	15	103680	—