数论_解题技巧

发表于 2023-11-21 更新于 2023-12-12 分类于解题技巧阅读次数： Waline：本文字数： 2.4k 阅读时长 ≈ 8 分钟

位运算

技巧

参见链接以及链接

练习题

P1469 异或的巧用
P1100 无符号移位

进制

技巧

参见链接

练习题

P1017 必须掌握的模板题！
P1143 n进制转m进制的范例，先把n进制转为十进制，再用短除法将十进制转为m进制

快速幂

技巧

参考链接

练习题

P1226 模板题
P1045 高精度与快速幂的结合

整除

技巧

参见链接，但是并不全...

补充几个关键性质：

若$a\shortmid b$且$b\shortmid c$，那么$a\shortmid c$
若$a\shortmid b$且$a\shortmid c$，那么对任意的整数x，y，有$a\shortmid bx+cy$
设整数$m\ne 0$，那么$a\shortmid b$等价于$ma\shortmid mb$
如果$k$是$n$的约数，那么$\frac{n}{k}$也一定是$n$的约数

只要限定$k\leqslant \frac{n}{k}$，即$k\leqslant \sqrt{n}$，就可以在$O\left( \sqrt{n} \right)$的时间复杂度内找到$n$的所有约数
对于约数、倍数相关的题目，经常用到枚举约数贡献和枚举倍数贡献两个切入点

练习题

P2926 对枚举约数和枚举倍数解题的思考

质数与合数

技巧

参考链接

质数和合数本身唯一常用的知识点就是：

若$a$为合数，则一定存在质数$p\shortmid a$，且$p\leqslant \sqrt{a}$

埃氏筛以此为核心实现的

还有一个易错点，虽然1不是质数，但是1与任何数互质！

模板

判断一个整数是否为质数的模板：

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

埃氏筛

一般用埃氏筛的思路解题较多，真正筛质数其实多用线性筛

for (int i = 2; i <= n; ++i) {
  if (!vis[i]) {  // 如果i没有被筛去，那么i是一个质数
    prime[++tot] = i;
    for (int j = i << 1; j <= n; j += i) {  // 枚举i的所有倍数j
      vis[j] = 1;                           // 质数i的倍数是合数
    }
  }
}

线性筛（欧拉筛）

除了筛质数，计算积性函数也是用它哟！

for (int i = 2; i <= n; ++i) {
  if (!vis[i]) prime[++tot] = i;  // 如果i没有被筛去，那么i是一个质数
  for (int j = 1; j <= tot && i * prime[j] <= n;
       ++j) {               // 枚举当前所有质数prime[j]
    vis[i * prime[j]] = 1;  // i的prime[j]倍是合数
    if (i % prime[j] == 0) break;
  }
}

练习题

P3383 线性筛模板题
P1835 区间筛的模板题，一定要会！
P7960 埃氏筛的灵活运用

最大公约数与最小公倍数

技巧

参见链接

总结一下常用结论：

对任意整数$m$，$m\left( a_1,\cdots ,a_k \right) =\left( ma_1,\cdots ,ma_k \right)$ 即整数同时成倍放大/缩小，最大公约数也放大/缩小相同倍数

该性质也同样适用于最小公倍数

可以发现，有$gcd\left( a,b \right) =e, gcd\left( \frac{a}{e},\frac{b}{e} \right) =1$存在；即$a$和$b$除掉最大公因数，两者将会互质
对任意整数$x$，$\left( a_1,a_2 \right) =\left( a_1,a_2+a_1x \right)$

即一个整数加/减上另一个整数的任意倍数，它们的最大公约数不变；其中$\left( a,0 \right) =a$

这是欧几里得算法（辗转相除法）的基础！

不适用最小公倍数
$\left( a_1,a_2,a_3,\cdots ,a_{k+r} \right) =\left( \left( a_1,\cdots ,a_k \right) ,\left( a_{k+1},\cdots ,a_{k+r} \right) \right)$ ，最大公约数的运算是满足“结合律”的

该性质也同样适用于最小公倍数
$\left[ a_1,a_2 \right] \times \left( a_1,a_2 \right) =a_1\times a_2$，即最大公约数×最小公倍数＝原来两个数的乘积

模板

求最大公约数的欧几里得算法（辗转相除法）不能处理负数，但是可以不区分a、b两个参数的大小

因为哪怕小了下一次递归就换回来了...

1	int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

求最小公倍数的话，用两数之积除以它们的最大公约数

1	int lcm(int x, int y) { return x / gcd(x, y) * y; } //先除后乘是为了防止溢出

练习题

P1029 枚举公约数的倍数，还是枚举公倍数的约数选择
P1072 枚举公约数的倍数，还是枚举公倍数的约数选择
P1414 最大公约数的性质
P1403 枚举约数个数
P1572 模拟分数计算时的通分和约分操作
P2651 模拟分数计算，细节有提升
P4057 最小公倍数的模拟题
P2660 最大公约数与分治、贪心的结合

算术基本定理

技巧

设$a>1$，那么必有$a={p_1}^{a_1}{p_2}^{a_2}\cdots {p_s}^{a_s}$

其中$p_j\left( 1\leqslant j\leqslant s \right)$是两两不相同的质数，$a_j\left( 1\leqslant j\leqslant s \right)$表示对应质数的幂次（出现的次数）

若在不计次序的意义下，该分解式是唯一的，俗称“分解质因数”；比如48＝2⁴×3

有以下重要推论，假定$a={p_1}^{a_1}{p_2}^{a_2}\cdots {p_s}^{a_s}$

$d$是$a$的约数的充要条件是$d={p_1}^{e_1}{p_2}^{e_2}\cdots {p_s}^{e_s},0\leqslant e_j\leqslant a_j,1\leqslant j\leqslant s$

即$d$中每个质数的幂次都不超过$a$的，每个质因子上的幂次直接决定了两数之间的整除性

例如12＝2²×3,72＝2³×3²，看到12的质因子上的每个幂次都对应地比72小，可以得到$12\shortmid 72$的结论

若$b={p_1}^{\beta _1}{p_2}^{\beta _2}\cdots {p_s}^{\beta _s}$（这里允许某些$a_j$或$\beta _j$为零），有最大公约数与最小公倍数的计算公式：

\[\left( a,b \right) ={p_1}^{\delta _1}{p_2}^{\delta _2}\cdots {p_s}^{\delta _s},\delta _j=\min \left( a_j,\beta _j \right) ,1\leqslant j\leqslant s\] \[\left[ a,b \right] ={p_1}^{\gamma _1}{p_2}^{\gamma _2}\cdots {p_s}^{\gamma _s},\gamma _j=\max \left( a_j,\beta _j \right) ,1\leqslant j\leqslant s\]

用$\tau \left( a \right)$表示$a$的所有正约数的个数，则$\tau \left( a \right) =\left( a_1+1 \right) \left( a_2+1 \right) \cdots \left( a_s+1 \right)$

比如a＝2⁷×3⁸×5⁹，直接可以写出a的因子个数等于＝(7+1)(8+1)(9+1)＝720个

用$\sigma \left( a \right)$表示$a$的所有正约数的和，有 $$ \sigma \left( a \right) =\small{\frac{{p_1}^{a_1+1}-1}{p_1-1}}\small{\frac{{p_2}^{a_2+1}-1}{p_2-1}}\cdots \small{\frac{{p_s}^{a_s+1}-1}{p_s-1}}=\left( 1+p_1+\cdots {p_1}^{a_1} \right) \left( 1+p_2+\cdots {p_2}^{a_2} \right) \cdots \left( 1+p_s+\cdots {p_s}^{a_s} \right) $$ 比如 $$ \sigma \left( 120 \right) =\frac{2^4-1}{2-1}\frac{3^2-1}{3-1}\frac{5^2-1}{5-1}=\left( 1+2+2^2+2^3 \right) \left( 1+3 \right) \left( 1+5 \right) $$

模板

分解质因数有很多写法，我列出我常用的：

for (int i = 2; i <= n / i; ++i) {
  if (n % i == 0) {
    pri[++tot] = i;
    while (n % i == 0) ++cnt[i], n /= i;
  }
}
if (n > 1) ++cnt[n], pri[++tot] = n;//有且只有一个大于根号n的质因数

练习题

P1069 算术基本定理的模板题

模意义下的运算

加减乘法没有什么特殊： \[ \left( a\pm b \right) \,\,mod\,\,M\,\,=\,\,\left( a\,\,mod\,\,M\,\,\pm \,\,b\,\,mod\,\,M \right) \,\,mod\,\,M \]

\[ \left( a\times b \right) \,\,mod\,\,M\,\,=\,\,\left( a\,\,mod\,\,M\,\,\times \,\,b\,\,mod\,\,M \right) \,\,mod\,\,M \]

除法不行，需要用到乘法逆元来转换

同余

若两数a，b除以m的余数相等，则称a，b模m同余，记作$a\equiv b\left( mod\,\,m \right)$

有如下重要特殊性质：

整除性：

$m\mid \,\,\left( a-b \right)$

简单证明一下：

a ＝ A ＋ xm，b ＝ B ＋ ym

由于a和b同余，那么A和B相等

显然a－b＝(x－y)m是m的倍数

反身性：

$a\equiv a\left( mod\,\,m \right)$

对称性：

若$a\equiv b\left( mod\,\,m \right)$ ，则$b\equiv a\left( mod\,\,m \right)$

传递性：

若$a\equiv b\left( mod\,\,m \right)$，$b\equiv c\left( mod\,\,m \right)$$，则$$a\equiv c\left( mod\,\,m \right)$

基本运算：

\[ \left. \begin{array}{r} a\equiv b\left( mod\,\,m \right)\\ c\equiv d\left( mod\,\,m \right)\\ \end{array} \right\} \Longrightarrow \begin{cases} a\pm c\equiv b\pm d\left( mod\,\,m \right)\\ ac\equiv bd\left( mod\,\,m \right)\\ \end{cases} \]

当$c = d$时，则为等量加法、减法：$a\pm c\equiv b\pm c\left( mod\,\,m \right)$

还有以下推导： \[ a\equiv b\left( mod\,\,m \right) \Rightarrow \begin{cases} an\equiv bn\left( mod\,\,m \right) ,\forall n\in \mathbb{Z}\\ a^n\equiv b^n\left( mod\,\,m \right) ,\forall n\in \mathbb{N} ^*,\text{不能逆推！}\\ P\left( a \right) \equiv P\left( b \right) \left( mod\,\,m \right) ,P\left( x \right) \text{为任意整系数多项式函数}\\ ak\equiv bk\left( mod\,\,mk \right) , k,m\in \mathbb{N} ^*\\ \frac{a}{d}\equiv \frac{b}{d}\left( mod\,\,\frac{m}{d} \right) , d\mid a,d\mid b,d\mid m\\ \text{若}n\mid m,\text{有}a\equiv b\left( mod\,\,n \right)\\ \end{cases} \]

除法：

\[ ac\equiv bc\left( mod\,\,m \right) \Rightarrow a\equiv b\left( mod\,\,m/gcd\left( c,m \right) \right) \]

稍微来证明一下方便记忆：

根据同余的整除性，有$m\mid \left( a-b \right) c$

根据整除的性质，两边同除$gcd\left( m,c \right)$整除性质保持不变

变成$\frac{m}{gcd\left( m,c \right)}\mid \frac{c}{gcd\left( m,c \right)}\cdot \left( a-b \right)$ 假设$gcd\left( m,c \right) =e$，那么$gcd\left( \frac{m}{e},\frac{c}{e} \right) =1$

所以$\frac{m}{gcd\left( m,c \right)}\bot \frac{c}{gcd\left( m,c \right)}$，$\frac{m}{gcd\left( m,c \right)}$的质因子与$\frac{c}{gcd\left( m,c \right)}$的质因子没有交集

故而推出$\frac{m}{gcd\left( m,c \right)}\mid \left( a-b \right)$

还有一个冷门性质： \[ a\equiv b\left( mod\,\,m_i \right) \left( i=1,2,\cdots ,n \right) \Rightarrow a\equiv b\left( mod\,\,lcm\left( m_1,m_2,\cdots ,m_n \right) \right) \]

乘法逆元

（后期更新）

练习题

P1593 算术基本定理+费马小定理+快速幂的结合

欧拉函数

技巧

（后期更新，链接虽然很多错，但还凑合）

练习题

P3601 根据欧拉函数定义，结合区间筛求出