No testdata at current.

CSP初赛 数学专题 炒鸡通俗版

由于猫鱼实在无法忍受原文字母满天飞，导致谁来了也在看天书，故编撰本文

猫鱼编 [github] [黑猫OJ] [homepage(敬请期待)]

整除

定义： $a，b ∈ Z$ ，$b ≠0$。如果有一个整数 $q$，使得 $a=bq$，则 $a$ 叫做 $b$ 的倍数，$b$ 叫做 $a$ 的因数。或者说 $b$ 能整除 $a$ 或者 $a$ 能被 $b$ 整除，记作 $b | a$。
如果 $b$ 不能整除 $a$，记作 $b ∤ a$。

定义：
若 $a$ $÷$ $b$ $=$ $x$ ······ $0$， 或者说 $a$ % $b$ $==$ $0$，
则 $a$ 能被 $b$ 整除。记作 $b$ | $a$，

叫做“ a 能被 b 整除 ” “b 能整除 a ”。注意区分标记处的顺序！
反之，不能整除，记作 $b ∤ a$
（ $a$, $b$, $x$ 均为整数，且$b ≠ 0$）

引理1：
若 $a，b，c ∈Z$ ，而 $a | b，b | c$，则 $a | c$。
证：$b = aq_1$，$c = bq_2$ ⇒ $c=a(q_1q_2)$

引理1：整除的传递性（四种表述）
若 $b$ 能被 $a$ 整除，$c$ 能被 $b$ 整除，则 $c$ 能被 $a$ 整除。
若 $a$ 能整除 $b$，$b$ 能整除 $c$ ，则 $a$ 能整除 $c$ 。
若 $b$ % $a$ == 0 and $c$ % $b$ == 0，则$c$ % $a$ == 0。
若 $a$ ÷ $b$ = 一个整数 ····· 0，$c$ ÷ $b$ = 一个整数 ····· 0，则$c$ ÷ $a$ = 一个整数 ······ 0
( $a$, $b$, $c$ 均为整数，且 $a≠0$，$b≠0$ )

写成符号语言：
若$a$∣$b$ 且 $b$∣$c$，则 $a$∣$c$。

证明：
因为 $a$ 能整除 $b$，则有 $b=a×k$ ①，其中 $k$ 是整数。
因为 $b$ 能整除 $c$，则有 $c=b×m$ ②，其中 $m$ 是整数。
① 代 ②，$c=a×k×m$
$k$，$m$ 均为整数，所以 $k×m$ 也为整数，所以： $c = a ×$ 一个整数
显然 $a$ 能整除 $c$

引理2：
证： $a，b ∈Z$，若 $|a| < |b|$，$|b| | |a|$，则 $a=0$。
如果 $|a|>0，0<|a|<|b|，|a|=|b|q$，如果 $q>0$，由于 $q ∈ Z$，$q ≥1$。
则 $|a| ≥|b|$，与 $|a|<|b|$ 矛盾，所以 $|a|=0$。

引理2：
一个整数无法被比它更大的数整除，$0$ 除外。

证明：
显而易见。如需请自行理解原文。

引理3：
带余除法：若 $a，b ∈Z，b≠0$，则一定有且只有两个整数 $q，r$，使得 $a = bq+r$，$0 ≤r<|b|$。
证：
1. 存在有一个整数 $q$，使得 $a=bq$，故 $r=0$，本引理成立。
2. $a = bq+r$，$0 ≤r<|b|$ 式子1
假设还有另外一对 $a=bq_1+ r_1$， $0 ≤r_1<|b|$ 式子2
两式相减，$0=b(q- q_1)+(r - r_1)$ 式子3
$|b| | | r - r_1 |$
$| r - r_1 |<|b|$
⇒ $r - r_1=0$
⇒ $r = r_1$
由式子3 和 $b≠0 ⇒ q =q_1$

引理3：带余除法（小学课本知识，可忽略）
任意整数 $a$ 除以非零整数 $b$，总能写出 唯一的 带余除法算式：

$$a ÷ b = c ······ d\quad (0 ≤ d < |c|，即余数小于商，c，d 均为整数)$$

此时：

$$a = b \times c + d \quad$$

证明：
显而易见。如需请自行理解原文。

质数与合数

编者注：这是为数不多原文就写的很明白的了，如果这都看不懂，就给我边蛙跳边背诵！
注意，只有大于1的正整数才有质数合数之分！！

定理：一个大于 $1$ 的正整数，只能被 $1$ 和自身整除，不能被其他正整数整除，这样的正整数叫做质数。
一个正整数，除了能被 $1$ 和自身整除外，还可以被其他的正整数整除，这样的正整数叫做合数。
如果一个正整数 $a$ 有一个因数 $b$，而 $b$ 又是质数，则 $b$ 就叫做 $a$ 的质因数。
全体正整数可以分为 3 类：

1. 整数 $1$ （编者注：所以1既不是质数也不是合数）
   
2. 全体质数
   
3. 全体合数
   
   

引理：如果 $a$ 是一个大于 $1$ 的整数，则 $a$ 的大于 1 的最小因数一定是质数。
证：
1.如果 $a$ 是一个质数，$a$ 的大于 $1$ 的因数只有一个，就是 $a$，结论成立。
2.如果 $a$ 是一个合数，除 $1$ 和 $a$ 之外，$a$ 还有其他正因数，假设 $b$ 是这些正因数中最小的，假定 $b$ 是合数，一定有 $1<c<b$，$c|b$，$b|a$，即 $c|a$，与假设矛盾。
此引理说明了：任何大于 $1$ 的整数都至少有一个质因数。

质因数分解

参考程序：

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        if (n % i == 0) {
            cout << n / i << endl;
            break;
        }
    }
        
	return 0;
}

引理：如果 $a$ 是一个大于 $1$ 的整数，而所有 ≤$\sqrt{a}$ 的数都除不尽 $a$，则 $a$ 是质数。

质数个数定理：定义 $π(x)$ 为不大于 $x$ 的质数的个数，$\lim\limits_{n\to\infty} \frac{π(x)}{\frac{x}{logx}}=1$

随着数的增大，质数的密度逐渐降低，且大约每 $\frac{x}{\ln x}$ 个数后有一个质数。
或者说，若随机选取一个不超过 $x$ 的整数，它是质数的概率约为 $\frac{1}{\ln x}$
注意！约为！！！

筛法求质数

朴素筛法：枚举 $2$ 到 $n$ 的每个数 $i$，将 $2i，3i，···$ 均标记为合数； 枚举完后仍没有被标记的数即为质数。

时间复杂度：$O(\sum\limits_{i=1}^n \frac{n}{i})=O(nlogn)$
简要证明：调和级数前 $n$ 项和 $≈logn$

$$f(n)=\sum\limits_{i=1}^n \frac{1}{i}=(\frac{1}{1})+(\frac{1}{2}+\frac{1}{3})+(\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7})+...$$

vector<int> get_primes(int n){
	vector<int> v;	
    for(int i = 2; i <= n; i++){
    	if(!book[i]) v.push_back(i);
        
        for(int j = 2 * i; j <= n; j += i)
            book[j] = true;
    }
    return v;
}

埃式筛法：（Eratosthenes筛法）只有质数才可能标记后面的合数。

时间复杂度：$O(nloglogn)$。

vector<int> get_primes(int n){
	vector<int> v;	
    
    for(int i = 2; i <= n; i++){
    	if(!book[i]) {
            v.push_back(i);
            
            for(int j = 2 * i; j <= n; j += i)
            	book[j] = true;
        } 
    }
    
    return v;
}

欧拉筛法：（线性筛法）设 $x$ 的最小质因数为 $d$，则 $x$ 只会被 $\frac{x}{d}$ 标记。

时间复杂度 $O(n)$。
当枚举到 $i$ 时，假设当前已经求出质数为 $P_1，P_2，… P_k$，而 $i$ 的最小质因数为 $P_m$，则对于所有的 $x∈[1,m]$，$P_x i$ 的最小质因数就是 $P_x$，故用 $i$ 标记 $P_x i$。

vector<int> get_primes(int n){
	vector<int> v;
  	for(int i = 2; i <= n; i++){
    	if(!book[i]) v.push_back(i);
      	for(int j = 0; v[j] <= n / i; j++){
        	book[v[j] * i] = true;
          	if(i % v[j] == 0) break;
        }
    }
  	return v;
}

最大公约数

定义：如果 $n ∈Z$，$n ≥2$，而 $a_1，a_2，⋅⋅⋅，a_n，d$ 都是正整数，又设 $d|a_1，d|a_2⋅⋅⋅d|a_n$ 则 $d$ 叫做 $a_1，a_2，⋅⋅⋅，a_n$ 的公约数，公约数中最大的一个叫做最大公约数，最大公约数是其他所有公约数的倍数，记作 $(a_1，a_2，⋅⋅⋅，a_n)=d$。

定义
一组正整数 $a_1,a_2,...,a_n$ 的共同约数（公约数）是指：

• 能同时整除所有这些数的正整数 $d$
• 最大公约数（GCD）是这些公约数中最大的那个，记作gcd(a,b)
• g根据定义，显然 $gcd(a,b) = gcd(b,a)$
• *最大公约数能被所有其他公约数整除

符号表示
$d$ 是 $a_1,a_2,...,a_n$ 的公约数 ⇨ $d|a_1$ 且 $d|a_2$ 且 ... 且 $d|a_n$
最大公约数记为 $(a_1,a_2,...,a_n) = d$

引理： $a，b$ 都是正整数，且 $a>b$，$a=bq+r$，$0<r<b$ ，其中 $q$ 和 $r$ 都是正整数，则 $a$ 和 $b$ 的最大公约数等于 $b$ 和 $r$ 的最大公约数，即 $(a,b)=(b,r)$。

引理（这就是辗转相除法）：
辗转相除法：求a与b的最大公因数：
a ÷ b = c ······ d，
重复用其除数(b)除以余数(d)。
直到余数为0，对应除法算式中的除数即为最大公因数

直观理解：
假设要找 28 和 16 的最大公约数：

1. 28 ÷ 16 = 1 余 12 → 转化为找 (16, 12)
   
2. 16 ÷ 12 = 1 余 4 → 转化为找 (12, 4)
   
3. 12 ÷ 4 = 3 余 0 → 找到 GCD 为 4
   

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

复杂度为 $O(log(max(a,b))$。
由于任何正整数都是 $0$ 和 $0$ 的公约数，故 $gcd(0, 0)$ 不存在。
对任意正整数 $a$，有 $gcd(0, a) = a$。

二进制算法：不断去除因子 $2$ 来降低常数。

int gcd(int a, int b){
    #编者注：这东西真的有学它的意义吗？他时间复杂度跟辗转相除法一样欸！
    #有背它的功夫，怎么不背我找到的进制转化极简模板？
	if(a == b) return a;
	if(a < b) return gcd(b, a);
	if(a % 2 == 0 && b % 2 == 0) return 2 * gcd(a / 2, b / 2);
	if(a % 2 == 0 && b % 2) return gcd(a / 2, b);
	if(a % 2 && b % 2 == 0) return gcd(a, b / 2);
	if(a % 2 && b % 2) return gcd(b, a - b);
}

最小公倍数

设 $a,b$ 为正整数，$m$ 为非负整数，若 $a | m$ 且 $b | m$，则称 $m$ 为 $a$ 和 $b$ 的公倍数。

定义

• 对于两个正整数 $a$ 和 $b$，它们的 公倍数 是能同时被 $a$ 和 $b$ 整除的数（例如：12 和 18 的公倍数有 36, 72, 108...）
  
• 最小公倍数（LCM） 是所有公倍数中最小的正数（比如 36 是 12 和 18 的最小公倍数），记作 $\text{lcm}(a, b)$
  
• 显然，$lcm(a,b)= lcm(b,a)$
  

lcm和gcd关系：$lcm(a,b)=\frac{ab}{gcd(a,b)}$
需要注意的是，在实际的代码实现中，为避免中间结果的溢出，应该使用 $a/gcd(a,b)*b$，而不是 $a*b/gcd(a,b)$。

算数基本定理（唯一分解定理）

设 $n≥2$ 为整数，则有唯一的分解式：$n = \prod\limits_{i=1}^m {P_i}^{\alpha_i}$，其中 $P_1<P_2<...<P_m$ 且 $P_i$ 为质数，$\alpha_i$ 为正整数。

编者注：我*这是啥呀，门？

任何一个合数，都可以拆成质数的乘积。
拆出的算式是唯一的。（不考虑顺序）

比如：

$$12 = 2×2×3 = 2^2×3$$

编者注：其与哥德巴赫猜想的区别

哥德巴赫猜想：每一个大于2的偶数是两个质数的和。

$$10 = 3 + 7 = 5 + 5$$

弱哥德巴赫猜想：任一大于 7 的奇数都可以写成三个 奇质数之和。

$$13 = 3 + 5 + 5$$

唯一分解定理：任何一个合数，都可以拆成质数的积，个数不限（为大于0的整数）

$$12 = 2×2×3 = 2^2×3$$

唯一分解定理是乘积，两种哥德巴赫猜想是和。
唯一分解定理分解结果个数不限，两种哥德巴赫猜想有个数要求。 </b>

证明（慎点，慎看，已无法简化）

1. 反证法起点：假设存在无法分解为质数乘积的最小整数 $n$
2. 性质分析：
   • $n$ 不能是质数（否则自身即分解式 $n = n$）
   • $n$ 必为合数，可表示为 $n = a \times b$（$1 < a, b < n$）
3. 矛盾推导：
   • 由于 $a, b < n$，根据假设它们都可分解为质数乘积
   • 因此 $n = a \times b$ 本身也能分解为质数乘积，与假设矛盾
   • 结论：所有 $n ≥ 2$ 均可质因数分解

唯一性证明（为什么分解唯一？）

1. 反证法起点：假设存在两种不同分解形式：

   $$n = p_1 p_2 \dots p_r = q_1 q_2 \dots q_s$$

$$$$

2. 欧几里得引理应用：
   • 质数 $p_1$ 整除右边乘积 ⇒ $p_1$ 必整除某个 $q_j$
   • 由于 $q_j$ 是质数 ⇒ $p_1 = q_j$
3. 递推消去：
   • 将两边相等的质数 $p_1 = q_j$ 约去，得到更小的数 $n'$
   • 重复此过程，最终所有质因子必须一一对应
4. 矛盾结论：
   • 若分解不唯一，则存在更小的数 $n'$ 满足矛盾条件
   • 与 $n$ 是"最小反例"的假设矛盾 ⇒ 唯一性得证 </b>

约数个数定理

$n$ 的约数个数 $d(n) = \prod\limits_{i=1}^m (\alpha_i+1)$
例如：$28=2^2 \times 7$
$d(28)=(2+1) \times (1+1)=6$

编者注：服了，又给我画扇门

如何计算一个数因数的个数？

1. 第一步：把数分解成质数相乘的形式
   （例如：28 = 2×2×7 = 2²×7¹）
   
   
2. 第二步：每个质数的右上角数字（指数）加1，再相乘
   
   • 2² → 指数是2 → 2+1=3
     
   • 7¹ → 指数是1 → 1+1=2
     
   • 总数 = 3×2=6个因数（实际是1,2,4,7,14,28）
     
     

为什么这样计算？

• 质数2有3种选择：用0次（2⁰=1）、1次（2¹=2）、2次（2²=4）
  
• 质数7有2种选择：用0次（7⁰=1）、1次（7¹=7）
  
• 所有组合方式共有3×2=6种，对应6个因数
  

---

约数和定理：
$n$ 的所有因数之和为：

$$S(n) = (1+p_1+p_1^2+\dots+p_1^{\alpha_1})(1+p_2+p_2^2+\dots+p_2^{\alpha_2})\dots$$

示例：$S(28) = (1+2+4)(1+7) = 56$

$$$$

通俗解释：
如何计算所有因数的和？

1. 第一步：对每个质数的各次幂求和
   
   • 对2²：$1+2+4 = 7$
     
   • 对7¹：$1+7 = 8$
     
     
2. 第二步：把这些和相乘
   $7 \times 8 = 56$（实际因数1+2+4+7+14+28=56）
   
   为什么这样计算？
   通过展开乘积可以得到所有组合：
   

$$(1+2+4)(1+7) = 1×1 + 1×7 + 2×1 + 2×7 + 4×1 + 4×7$$

这正好对应所有因数：1,7,2,14,4,28

---

更多例子验证

数	质因数分解	因数个数计算	实际因数	因数和计算	实际和
6	2¹×3¹	(1+1)(1+1)=4	1,2,3,6	(1+2)(1+3)=12	12
12	2²×3¹	(2+1)(1+1)=6	1,2,3,4,6,12	(1+2+4)(1+3)=28	28
30	2¹×3¹×5¹	(1+1)(1+1)(1+1)=8	1,2,3,5,6,10,15,30	(1+2)(1+3)(1+5)=72	72

裴蜀定理

对于不定方程 $ax+by=m$, 其有解的充要条件 $gcd(a,b) | m$。

不定方程的定义：

1. 未知数的个数多于方程个数
2. 未知数受到条件要求（如要求是有理数、整数或正整数等等）

当方程 $ax + by = m$（其中$a,b,m$是整数已知数）存在整数解时
$gcd(a,b) | m$，或者说$m$ $\%$ $gcd(a,b) == 0$

---

重要推论：当 $a$，$b$ 互质时，$a$，$b$ 的整系数线性组合可以得到所有的整数。

当$a$与$b$互质，即$gcd(a,b) = 1$时,$ax + by$可以等于任意整数

• 例如：$3x + 2y$可以等于1（取x=1,y=-1）、-1、5等所有整数

符号语言：
当$\gcd(a,b)=1$时，对任意整数$m$，存在整数$x,y$使$ax + by = m$