一、整数性质

1. 带余除法

设 a、b 为整数，b!=0，则存在整数 q 和 r，使得 a = b*q + r，其中 0<=r<|b|，并且 q 和 r 由上述条件唯一确定；整数 q 被称为 a 被 b 除得的商，数 r 称为 a 被 b 除得的余数。

其中，r = 0 时，视为 a 被 b 整除。

带余除法的核心是关于余数 r 的取值范围不等式：0<=r<|b|，显然 r 有 |b|种取值。

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

任何一个大于 1 的正整数 a，能唯一的表示成质（素）因数的乘积（不计较因数的排列顺序）即可以唯一地写成下面：

$a = p^{a1}_1 * p^{a2}_2 ⋯ p^{a^k}_{k}$

其中 $p_i$ 为素数（$p_i < p_j (i < j)），a_i ∈ N_+ ，i = 1,2,…,k。$ 本式被称为整数 a 的标准分解式。

3. 其他

• 任何一个正整数 n，都可以写成$n = 2^m * l$的形式，其中 m 为非负整数，l 是奇数。
• 若 a∈Z，a>1，则 a 的除 1 以外的最小正因数 q 是一个质数。如果 q!=a,则 q<= $\sqrt{a}$。推论：如果不超过 a 的所有质数均不是 a 的约数，则 a 必为质数。

二、整除

1. 常见的整除判定方法

1.一个数的末位能被 2 或 5 整除，这个数就能被 2 或 5 整除；一个数的末两位能被 4或 25 整除，这个数就能被 4 或者 25 整除；一个数的末三位能被 8 或 125 整除，这个数就能被 8 或 125 整除。

2.一个数各位数字之和能被 3 整除，这个数就能被 3 整除；一个数各位数字之和能被 9 整除，这个数就能被 9 整除。

3.如果一个数的奇数位上的数字之和与偶数位上的数字之和的差能被 11 整除，那么这个数能被 11 整除。

4.如果一个整数的末三位与末三位以前的数字组成的数之差能被 7、11 或 13 整除，那 么这个数能被 7、11 或 13 整除。

5.如果一个数能被 99 整除，这个数从后两位开始两位一截所得到的所有数（如果有偶数位，则拆出的数都是两位数；如果有奇数位，则拆出的数中有若干个两位数，还有一个是一位数）的和是 99 的倍数，这个数一定是 99 的倍数。

2. 整除的性质

1.性质 1：如果数 a 和数 b 都能被数 c 整除，那么它们的和或差也能被 c 整除。即如果 c|a 且 c|b，那么 c|（a±b）。

2.性质 2：如果数 a 能被数 b 整除，b 又能被数 c 整除，那么 a 也能被 b 或 c 整除。即如果 b|a，c|b，那么 c|a。

3.性质 3：如果数 a 能被数 b 与数 c 的积整除，那么 a 也能被 b 或 c 整除。即如果 bc|a，那么 b|a 或 c|a。

4.性质 4：如果数 a 能被数 b 整除，也能被数 c 整除，且数 b 和数 c 互质，那么 a 一定能被 b 与 c 的乘积整除。即如果 b|a，c|a，且（b，c）= 1，那么 bc|a。

5.性质 5：如果数 a 能被数 b 整除，那么 am 也能被 bm 整除。如果 b|a，那么 bm|am（m是非 0 整数）。

6.性质 6：如果数 a 能被数 b 整除，且数 c 能被数 d 整除，那么 ac 也能被 bd 整除。如果 b|a，且 d|c，那么 bd|ac。

三、余数

1. 余数三大余数定理

• 加法定理： (a+b)%c = （a%c + b%c）%c
• 减法定理： (a-b)%c = （a%c - b%c）%c
• 乘法定理：（a*b）%c = (a%c) * (b%c) %c

2. 同余

1. 定义：若两个整数 a、b 被自然数 m 除有相同的余数，那么称 a、b 对于模 m 同余。

2.重要推论：如果 a 和 b 对 m 同余，则 a 和 b 的差可以被 m 整除。即如果 a≡b（modm），那么一定存在 a-b=m*k。

3.余数判别法： 求 a%b 时，当 a 的位数较多时，可以利用同余减轻运算压力。余数判别法和上面学的整数判定方法类似，例如，求整数 N 被 2 或 5 除的余数等于 N 的个位数被 2 或 5 除的余数。其他的也类似，类比整数判定法记忆即可。

四、约数

1. 约数定义

约数是指能够整除一个数的正整数，也就是说，如果一个正整数 a 能够被另一个正整数b 整除，那么 b 就是 a 的约数。

2. 筛选一个数的约数

简单性质：若 d>= $\sqrt{n}$是 n 的约数，则 n/d<= $\sqrt{n}$也是 n 的约数，即约数总是成对出现。

筛法：根据上一条性质，枚举 d=1 到 $\sqrt{n}$ 之间所有数是否能整除 n 即可（n%d=0 说明n 能被 d 整除），若 d 能整除 n 则 d 和 n/d 都是 n 的约数。算法复杂度O( $\sqrt{n}$)。

五、素数（质数）

1. 素数定义

素数是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。

2. 素数判定

方法 1：对于一个数 n，直接枚举 2 到 n-1 是否能整除 n 即可。时间复杂度 O（n）。

方法 2：根据因数简单性质，因数总是成对出现的，因此对于一个数 n，只需枚举2 到 $\sqrt{n}$是否能整除 n 即可。时间复杂度 O（ $\sqrt{n}$）。

方法 3：Miller-Rabin 素数判定，用于判定特别大的一个数是不是素数，需要注意的是，它只是大概率可以测出一个数是不是素数，并非非常准确的判定素数算法。具体做法不再赘述。

3. 素数筛法

埃式筛法：

基本思想：素数的倍数一定不是素数。

实现方法：使用一个 vis[]标记数组标记一个数是否是素数（初始化为 0 表示是素数，1 表示不是素数），从小到大枚举每一个素数 x，把 x 的倍数都标记为 1。

时间复杂度：筛一个 n 范围内的素数时，时间复杂度为 O（nloglogn）

线性筛法（欧拉筛）：

基本思想：每个合数只被它最小的素因子筛一次。

实现方法：改进埃式筛法，选用最小的素因子筛即可。

时间复杂度：筛一个 n 范围内的素数时，时间复杂度为 O（n）

4. 素数性质

1.素数 p 的约数只有两个：1 和 p。

2.任一大于 1 的自然数，要么本身是素数，要么可以分解为几个素数之积，且这种分解是唯一的。

3.素数的个数是无限的。

4.素数的个数公式π（x）是不减函数。

5.若 n 为正整数，在 n* n 到(n+1) * (n+1)* (n+1)之间至少有一个素数。

6.若 n 为大于或等于 2 的正整数，在 n 到 n！之间至少有一个素数。

7.若素数 p 为不超过 n（n>=4）的最大素数，则 p>n/2。

五、分解质因数

把一个合数分解为若干个质因数乘积的过程叫做分解质因数。

做法：分解 n，就从最小的素数 x 开始枚举，若 n 可以被 x 整除，就使得 n=n/x 重复这 个过程；若 n 不可以被 x 整除，枚举下一个大一点的素数，直到 n 被除为 0 为止。

六、最大公约数与最小公倍数

1. 定义

最大公约数：设有整数 a，b，……，c 不全为 0，同时整除它们的数被称为它们的公约数。其中最大的那一个被称为最大公约数，用符号（a，b，……，c）表示。

（a，b，……，c）= 1 时称 a，b，……，c 互素。

互素并不等价于两两互素，两两互素可以推出（a，b，……，c）= 1，而（a，b，……，c）= 1 不能推出两两互素。

最小公倍数：设有整数 a，b，……，c 均是非 0 整数，一个同时为它们倍数的数称为它们的公倍数。其中最小的哪一个被称为最小公倍数，用符号[a，b，……，c]表示。

2. 性质

1.a、b 的任何一个公约数都是它们最大公约数的约数。

2.a、b 的任何一个公倍数都是它们最小公倍数的倍数。

3.若 b 是正整数，则(0,b) = b，[1,b]=b。

4.对于任意的整数 x，有(a,b)=（a,b+ax）。

5.两个整数的最大公约数与最小公倍数满足：（a,b）* [a,b] = |a * b|

3. 求法

由于（a,b）* [a,b] = |a* b|，我们更关注最大公因数的求法，知道最大公因数后可以 由此公式得出最小公倍数。

求最大公因数的两种方法：

1. 枚举（不常用）

2. 辗转相除法：

可以证明 gcd(a,b) == gcd(b,a%b)(a>b)所有有以下代码：

int gcd(int a, int b) {
	if(b==0)
		return a;
	return gcd(b, a%b);
}

时间复杂度为 log 级别的复杂度

七、习题

1. 下面是根据欧几里得算法编写的函数，它计算的是 a 和 b 的()。

   int euclid(int a, int b) {   
       if (b == 0)   
           return a;   
       else   
           return euclid(b, a % b);   
   }
   

{{ select(1) }}

• 最大公共素因子
• 最小公共素因子
• 最大公约数
• 最小公倍数

2. 10000 以内，与 10000 互质的正整数有()个。

{{ select(2) }}

• 2000
• 4000
• 6000
• 8000

3. 从 1 到 2018 这 2018 个数中，共有( {{ input(3) }})个包含数字 8 的数。