数论

数论的核心是整除、互素、同余。

整除：$a$ 可以整除 b $\Leftrightarrow a\mid b$ 即 $b\bmod a=0$。（正负都可）

性质（以下都是整数）：

• 传递性：$a\mid b,b\mid c\Rightarrow a\mid c$。

• 线性组合：$a\mid b,a\mid c\Rightarrow a\mid(mb+nc)$。

• 写成等式： $a\mid b \Leftrightarrow ka=b.$

互素：$\gcd(a,b)=1\Leftrightarrow a\perp b$，即 $a,b$ 互素。重要性质：

• $x\mid ab,x\perp b\Rightarrow x\mid a$。

同余：$a\bmod n=b\bmod n$，也可以写成 $a\equiv b\pmod n$。

• $a\equiv b\pmod n\Leftrightarrow n\mid(a-b)$。
• 注意：$0\bmod m=m$。
• 写成等式： $a\bmod b=d\Leftrightarrow a=ka+d$，

剩余系： 完全模 $m$ 剩余系是指：$$

最大公因数 GCD

$\gcd(a,b)$ 表示 $a,b$ 的最大公因数。

求 $\gcd$ 可以用 std::__gcd()。如果要自己搓，常用欧几里得算法，又叫辗转相除法，即 $\gcd(a,b)=\gcd(b,a\mod b)$。

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

$\gcd$ 的性质：

• 结合律：$\gcd(\gcd(a,b),c)=\gcd(a,\gcd(b,c))=\gcd(a,b,c)$。交换律当然也有。

• $\gcd(ma,mb)=m\gcd(a,b)$。

• $\cfrac{a}{\gcd(a,b)}\perp\cfrac{b}{\gcd(a,b)}.$

裴蜀定理

裴蜀定理：对于已知的整数 $a,b$，存在整数 $x,y$ 使得 $ax+by=\gcd(a,b)$。

推论：

• $a\perp b$ 当且仅当 $ax+by=1.$

• $ax+by=d$ 有解（$a,b$ 已知），当且仅当 $d=k\gcd(a,b).$（二元线性丢番图方程）

裴蜀定理很好证明：

• 对任意 $x,y$，$xa+by=d$，则 $d=k\gcd(a,b)$，$k$ 是整数。

• 为什么？因为 $\gcd(a,b)(xr_1+yr_2)=d$。容易看出：最小的 $d$ 是 $\gcd(a,b)$，当且仅当 $xr_1+yr_2=1$。（这里 $r_1,r_2$ 是互素的。）

裴蜀定理主要用于解决形如 $ax+by=d$ 这样的线性组合问题。

同余式

如果 $a\equiv b\pmod m$，$a,b,c,d$ 都是整数，则有：

• $a\pm c\equiv b\pm d\pmod m.$

• $ac\equiv bd \pmod m.$

• $a^k\equiv b^k\pmod m$，注意 $k$ 是正整数。

• 不保证 $\cfrac{a}{c}\equiv\cfrac{b}{c}\pmod m$ 成立。

单位元、逆元

单位元： 对于一种二元运算 $f(a,b)$，定义域为 $S$，如果 $\forall a\in S$，$f(a,e)=a$，则称 $e$ 为这种二元运算 $f$ 的单位元。

更准确地说，$f(a,b)$ 不一定满足交换律，即 $f(a,b)=f(b,a)$ 不一定成立。所以逆元分为两种：左单位元 $f(e_1,a)=a$、右单位元 $f(a,e_2)=a$。

逆元： 如果 $f(a,b)=a$，则 $a,b$ 互为逆元。

算数基本定理

任何 $\gt1$ 的正整数都有且仅有一个有限个素数的乘积（即素数分解）：$n=p_1^{c_1}\times p_2^{c_2}\times\dots\times p_m^{c_m}$。

数论函数（算术函数）

指定义域是 $\mathbb{N}_+$ 的函数。

积性函数

积性函数是数论函数。如果对于所有互素的正整数 $a,b$，函数 $f(ab)=f(a)f(b)$，就称 $f(x)$ 为积性函数。

如果对于不互素的正整数 $a,b$ 也能成立，就称为完全积性函数。

性质：

• $f(1)=1$。

常用积性函数：

• 单位函数：$\text{id}(n)=n.$

• 幂函数：$I_k(n)=n^k.$（就是说 $(mn)^k=m^kn^k$）

• 因数和函数：$\sigma(n)=\sum_{d\mid n}d.$

• 因数个数：$d(n)=\sum_{d\mid n}1.$

欧拉函数

欧拉函数记作：$\phi(x)$。手写：$\varphi(x)$。利用欧拉函数可以推导出欧拉定理（比较重要）。

$\phi(n)$ 定义为：不超过 $n$ 的、与 $n$ 互素的正整数个数。

$$\phi(n)=\sum_{i=1}^n[i\perp n]$$

注意：这里 $[\space]$ 是计数的意思，括号内的式子成立取 $1$，反之取 $0$。

欧拉函数的几个定理（我不会证）：

• 欧拉函数是积性函数。

• 设 $n$ 为正整数，则 $n=\sum_{d|n}\phi(d).$

• 求欧拉函数：假设 $n$ 可以分解为 $k$ 个素数的乘积，即

$$n=p_1^{c_1}\times p_2^{c_2}\times\dots p_k^{c_k},\\ \Rightarrow \phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_k})=n\prod_{i=1}^k(1-\frac{1}{p_i}).$$

整除分块 / 数论分块

整除分块用于解决这个问题：求 $\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor$。