数学笔记全文

修订

平面几何

Menelaus 梅涅劳斯定理

Ceva 塞瓦定理

Stewart 定理

调和点列

1. $\frac{1}{AC}+\frac{1}{AD}=\frac{2}{AB}$，即 $AB$ 的长度是 $AC$ 和 $AD$ 长度的调和平均值。
2. $AB\cdot CD=2AD\cdot BC=2AC\cdot DB$
3. $CA\cdot CB=CM\cdot CD$，$DA\cdot DB=DM\cdot DC$
4. $MA^2=MB^2=MC\cdot MD$

内切圆和调和点列

极线和调和点列

线性规划

例题 1

基本概念

1. 约束条件：变量 $x,y,\dots$ 满足的一组条件，上述二元一次不等式组就是对 $x,y$ 的约束条件。
2. 线性约束条件：由变量 $x,y,\dots$ 的一次不等式 / 方程组成的不等式组就称为线性约束条件，如上述二元一次不等式。
3. 目标函数：欲求最大值或最小值所涉及的变量 $x,y,\dots$ 的解析式，如上述 $z$。
4. 线性目标函数：目标函数关于变量 $x,y,\dots$ 的一次解析式，如上述 $z$。
5. 线性规划问题：在线性约束条件下求线性目标函数的问题。
6. 可行解：满足线性约束条件的解 $(x,y)$。
7. 可行域：由所有可行解组成的集合。
8. 最优解：使目标函数取得 $\max$ 或 $\min$ 的可行解。

解法

1. 画图，数形结合。
   $\begin{cases}5x-11y \geq -22 & \implies y \leq \frac{5}{11}x + \frac{1}{2} & \implies & y = \frac{5}{11}x + \frac{1}{2}\ 图像的下边 \\ 2x+3y \geq 9 & \implies y \geq -\frac{2}{3}x + 3 & \implies & y = -\frac{2}{3}x + 3\ 图像的上边 \\ 2x \leq 11 & \implies x \leq \frac{11}{2} & \implies & x=\frac{11}{2}\ 图像的左边 \end{cases}$
   在平面直角坐标系上画出对应的平面区域 （ 可行域 ），再把目标函数 $z=ax+by$ 变形为 $y=-\frac{a}{b}x + \frac{z}{b}$，$\\$ 所以求 $z$ 的最值可看成是求直线 $y=-\frac{a}{b}x + \frac{z}{b}$ 在 $y$ 轴上截距的最值。以这题为例，$\\ z=10x+10y \implies y= -x + \frac{z}{10}$ 容易证明，当 $z=85$ 时 $y$ 轴上截距取最值，所以 $\max{z}=85.$
   
2. 仔细观察，可以发现最优解非常容易出现在可行域构成的多面体的顶点处。

例题 2

• 求 $(2x+y)_{\mathrm{min}}$：$x_{\min}=a \implies y_{\min}=a \implies (2x+y)_{\mathrm{min}}=3a$
• 求 $(2x+y)_{\mathrm{max}}$：$\begin{cases}x-y\leq 0 \\ x+y\leq 2\end{cases}\xRightarrow{\mathrm{Add\ }} x\leq 1\implies y\leq 1\implies (2x+y)_{\mathrm{max}}=3$
• $3=4\times 3a\implies a=\frac{1}{4}$

例题 3（ 2024 九省联考 T14 ）

• 注意到 $c$ 的约束条件是最少的，首先考虑消去它，得到

• 作出可行域：$\mathrm{and}$ 连接的区域之间取交，$\mathrm{or}$ 连接的区域之间取并。阴影部分即为可行域。

• 回到题目，要求 $M=\max{\set{y-x,\frac{1-y}{2}}}$，我们需要知道何时 $M=y-x$，何时 $M=\frac{1-y}{2}$

• 因为最终要求的是 $M$ 的最小值，所以对蓝色区域而言，$y$ 尽量小，$x$ 尽量大，根据例题 1 的经验，这样的极值点通常出现在多边形的顶点处，经过比较后 $P$ 点是极值点，此时 $M=0.2$。对绿色区域而言，只需满足 $y$ 尽量大，显然，$P$ 点也是极值点。
• 综上所述，$\max{\set{b-a,c-b,1-c}}$ 的最小值 $=\frac{1}{5}$。

数论

质数

• 定义：一个正整数无法被除了 $1$ 和它自身之外的任何自然数整除，则成为质数，否则为合数。
• 数量：对于一个足够大的整数 $N$，不超过 $N$ 的质数有 $\pi(x)\approx\frac{N}{\ln N}$ 个，所以第 $n$ 个质数约为 $n\ln n$。
• 判定：试除法，若 $N$ 为合数，则存在一个能整除 $N$ 的数 $T$ 且 $2 \leq T \leq \sqrt{N}$。
• 算数基本定理：$N = p_1^{c_1}p_2^{c_2}\dots p_n^{c_n}$，$N$ 的正约数个数 $=\displaystyle\prod_{i=1}^{n}(c_i+1)$，
  $N$ 的所有正约数的和 $=\displaystyle\prod_{i=1}^{n}(\displaystyle\sum_{j=0}^{c_i}(p_i)^j)$。
  一个正整数 $N$ 的约数个数上界为 $2\sqrt{N}$，$1$ ~ $N$ 每个数的约数个数的总和大约为 $N\log N$。

因数

整除

1. 若 $a\mid b$ 且 $a\mid c$，则 $\forall x,y$，有 $a\mid xb+yc$。
2. 若 $a\mid b$ 且 $b\mid c$，则 $a\mid c$。
3. 若 $a\mid b$ 且 $b\mid a$，则 $a=\pm b$。
4. 设 $m\neq 0$，则 $a\mid b$，当且仅当 $ma\mid mb$。

最大公因数与最小公倍数

• $\forall a,b\in\N,\ \gcd(a,b)\cdot\mathrm{lcm}(a,b)=ab$

• 九章算术 更相减损术： $\gcd(a,b)=\gcd(b,a-b)=\gcd(a,a-b),\gcd(2a,2b)=2\gcd(a,b)$。

• 欧几里得算法：$\forall a,b\in\N,b\neq 0,\gcd(a,b)=\gcd(b,a\ \mathrm{mod}\ b)$。

1. 若 $a<b$，则有 $\gcd(b,a\ \mathrm{mod}\ b)=\gcd(b,a)=\gcd(a,b)$。
2. 若 $a\geq b$，不妨设 $a=q\cdot b+r\ (0\leq r<b)$。显然 $r=a\ \mathrm{mod}\ b$。对于 $a,b$ 的任意公因数 $d$，$\\$ 因为 $d\mid a,d\mid q\cdot b$，故 $d\mid (a-q\cdot b)$，即 $d\mid r$。因此 $d$ 也是 $b,r$ 的公因数，反之亦成立。$\\$ 故 $a,b$ 的公因数集合与 $b,a\ \mathrm{mod}\ b$ 的公因数集合相同。于是它们的最大公因数也相等。

欧拉函数

1. $\forall n>1$，$1$ ~ $n$ 中与 $n$ 互质的数的和为 $\frac{n\times\varphi(n)}{2}$。
2. 若 $a,b$ 互质，则 $\varphi(ab)=\varphi(a)\varphi(b)$。
3. 设 $p$ 为质数，$\varphi(p)=p-1$。
4. 设 $p$ 为质数，$k\in\N^*,\varphi(p^k)=p^{k-1}\times(p-1)=p^k-p^{k-1}$。
5. 设 $p$ 为质数，若 $p\mid n$ 且 $p^2\mid n$，则 $\varphi(n)=\varphi(\frac{n}{p})\times p$。
6. 设 $p$ 为质数，若 $p\mid n$ 但 $p^2\nmid n$，则 $\varphi(n)=\varphi(\frac{n}{p})\times (p-1)$。
7. 若 $n$ 为奇数，则 $\varphi(2n)=\varphi(n)$。
8. $\forall n\geq 3,\ n\in\N^*,\ 2\mid\varphi(n)$。
9. 欧拉反演：$\displaystyle\sum_{d\mid n}\varphi(d)=n$。

1. 因为 $\gcd(n,x)=\gcd(n,n-x)$，所以与 $n$ 不互质的数 $x,n-x$ 成对出现，平均值为 $\frac{n}{2}$。$\\$ 因此与 $n$ 互质的数的平均值也是 $\frac{n}{2}$，进而得到性质 1。
2. 根据欧拉函数的计算式可直接获得性质 2。
3. 根据欧拉函数的定义可直接获得性质 3。
4. 从 $1$ ~ $p^{k}$ 中的所有数，除了 $p^{k-1}$ 个 $p$ 的倍数外都与 $p^k$ 互素。
5. 若 $p\mid n$ 且 $p^2\mid n$，则 $n,\frac{n}{p}$ 包含相同的质因子，只是 $p$ 的指数不同。$\\$ 按照欧拉函数的计算公式，$\frac{\varphi(n)}{\varphi(\frac{n}{p})}=\frac{n}{\frac{n}{p}}=p$，得到性质 5。
6. 若 $p\mid n$ 且 $p^2\mid n$，则 $n,\frac{n}{p}$ 互质。因为 $\varphi(n)=\varphi(\frac{n}{p})\varphi(p)$，而 $\varphi(p)=p-1$，得到性质 6。
7. $\forall m<2n,m\in\N^*$，若 $2\mid m$，则 $\gcd(m,2n)\neq 1$，也就是对欧拉函数的值没有贡献；$\\$若 $2\nmid m$，则 $\gcd(m,2n)=1$，欧拉函数的值也就与 $2n$ 中的偶质因子无关。
8. $n\geq 3$ 时，与 $n$ 互质的数不可能为 $\frac{n}{2}\implies\forall x<n,\gcd(x,n)=\gcd(n-x,n)$，也就是存在一一对应关系。
9. 设 $f(n)=\displaystyle\sum_{d\mid n}\varphi(d)$，利用 $\varphi$ 是积性函数，得到：$\\$若 $n,m$ 互质，则 $f(nm)=\displaystyle\sum_{d\mid nm}\varphi(d)=\displaystyle\sum_{d\mid n}\varphi(d)\cdot\displaystyle\sum_{d\mid m}\varphi(d)=f(n)f(m)$，即 $f(n)$ 是积性函数。$\\$ 对于单个质因子有：$\begin{aligned}f(p^m)&=\displaystyle\sum_{d\mid p^m}\varphi(d)=\displaystyle\sum_{i=0}^{m}\varphi(p^i)=\varphi(1)+\varphi(p)+\varphi(p^2)+\varphi(p^3)+\dots+\varphi(p^m)\\&= 1+(p-1)+(p-1)p+(p-1)p^2+\dots+(p-1)p^{m-1}\\&=1+(p-1)+(p^2-p)+(p^3-p^2)+\dots+(p^m-p^{m-1})=p^m\end{aligned} \\$ 所以 $f(n)=\displaystyle\prod_{i=1}^{m}f(p_i^{c_i})=\displaystyle\prod_{i=1}^{m}p_i^{c_i}=n$

积性函数与完全积性函数

1. 若 $f(x)$ 和 $g(x)$ 均为积性函数，则以下函数也为积性函数： $\begin{aligned}h(x)&=f(x^p) \\ h(x)&=f^p(x) \\ h(x)&=f(x)g(x) \\ h(x)&=\displaystyle\sum_{d\mid x}f(d)g(\frac{x}{d})\end{aligned}$
2. 设 $x=\displaystyle\prod p_i^{c_i}$，
   若 $f(x)$ 为积性函数，则 $f(x)=\displaystyle\prod f(p_i^{c_i})$。
   若 $f(x)$ 为完全积性函数，则 $f(x)=\displaystyle\prod f^{c_i}(p_i)$。

同余

费马小定理与欧拉定理

• 费马小定理：若 $p$ 是质数，则对于任意整数 $a$，有 $a^p\equiv a\ (\mathrm{mod}\ p)$。
• 欧拉定理：若正整数 $a,n$ 互质，则 $a^{\varphi(n)}\equiv 1\ (\mathrm{mod}\ n)$。

• 欧拉定理的推论：若正整数 $a,n$ 互质，则对于任意正整数 $b$，有 $a^b\equiv a^{b\ \mathrm{mod}\ \varphi(n)}\ (\mathrm{mod}\ n)$

• 扩展欧拉定理
  $a^b\equiv\begin{cases}a^{b\ \mathrm{mod}\ \varphi(m)}&\text{if }\gcd(a,m)=1\\ a^b&\text{if }\gcd(a,m)\neq 1,b<\varphi(m)\\ a^{b\ \mathrm{mod}\ \varphi(m)+\varphi(m)}&\text{if }\gcd(a,m)\neq 1,b\geq\varphi(m)\end{cases}\ (\mathrm{mod}\ m)$
  证明十分显然，略。

• 若正整数 $a,n$ 互质，则满足 $a^x\equiv 1\ (\mathrm{mod}\ n)$ 的最小正整数 $x_0$ 是 $\varphi(n)$ 的约数。

中国剩余定理

威尔逊定理

• $p$ 为素数 $\xLeftrightarrow{}(p-1)!\equiv -1\ (\mathrm{mod}\ p)$

1. 充分性
   对于 $p$ 不是素数的情况，有 $\begin{cases} p=1 & (1-1)!\equiv 0\ (\mathrm{mod}\ 1) \\ p=4 & (4-1)!\equiv 2\ (\mathrm{mod}\ 4) \\ p>4 & 分类讨论得出\ (p-1)!\equiv 0\ (\mathrm{mod}\ p) \end{cases}$
   (a) 当 $p$ 为完全平方数。
   则 $p=k^2$ 且 $k>2$，用相减法比较 $2k$ 与 $p$ 的大小得 $2k<p$，于是有
   $\begin{aligned}(p-1)!&=1\times 2\times\dots\times k\times\dots\times 2k\times\dots\times (p-1)\\ &=2nk^2\\&=2np\end{aligned}$
   所以 $(p-1)!\equiv 0\ (\mathrm{mod}\ p)$ 且 $p$ 为完全平方数。
   (b) 当 $p$ 不为完全平方数。
   则 $p$ 可以表示为两个不相等的数 $a$ 和 $b$ 的乘积，设 $a<b$，则有 $p=ab,1<a<b<p$
   $\begin{aligned}(p-1)!&=1\times 2\times\dots\times a\times\dots\times b\times\dots\times (p-1)\\&=a\times b\times n\\ &=np\end{aligned}$
   所以 $(p-1)!\equiv 0\ (\mathrm{mod}\ p)$ 且 $p$ 不为完全平方数。
2. 必要性
   当 $p$ 为素数时，考虑二次剩余式 $x^2\equiv 1\ (\mathrm{mod}\ p)$，化简得 $(x-1)(x+1)\equiv 0\ (\mathrm{mod}\ p)$
   于是 $x\equiv 1\ (\mathrm{mod}\ p)$ 或 $x\equiv p-1\ (\mathrm{mod}\ p)$。现在先抛开 $1$ 和 $p-1$ 不管，
   $\forall a\in [2,p-2]$，必然存在一个和它不相等的逆元 $a^{-1}\in[2,p-2]$，满足 $aa^{-1}\equiv 1\ (\mathrm{mod}\ p)$
   所以必然有 $\frac{p-3}{2}$ 对数相乘的乘积为 $1$，即 $(p-2)!\equiv 1\ (\mathrm{mod}\ p)$
   等式两边同时乘 $p-1$ 就得到威尔逊定理。