近4年CSPJ考察情况：

	题号	题型	分值
2020	第13题	单项选择	2分

难易度：中等

整除

设 有整数 a,b 且 a 不等于 0。

如果存在整数 q，使得 b=aq，那么就说 b 可被 a 整除，记作 a∣b，b 不被 a 整除记作 a∤b。

比如 3∣9 的意思是 3 能整除 9 ， 而 3∤10 是3不能整除 10。

🌰 给定两个正整数a,b(0<a,b<10^5), 判断 a 能否整除 b。

if (b % a == 0) {
    printf("a 能整除 b");
} else {
	printf("a 不能整除 b");
}

⚡快问快答 题目数量 X 3

1、5 % 3 = ？
A 、2
B、1
C、0

2、3 % 12 = ？
A、3
B、0
C、12

3、0 % 17 = ？
A、0
B、17
C、13

取模和取余

C/C++中的运算符 % 其实是取余运算，只是习惯上读作取模。

取余(rem)，遵循尽可能让商向0靠近的原则

取模(mod)，遵循尽可能让商向负无穷靠近的原则

符号相同时，两者不会冲突。

比如，7 ÷ 3 = 2.3，产生了两个商2和3。

7 =3 * 2 + 1 或 7 = 3 * 3 + (-2)。

因此，7 rem 3 = 1，7 mod 3= 1。

符号不同时，两者会产生冲突。

比如，7 ÷ (-3) = -2.3， 产生了两个商 -2 和 -3。

7=(-3) * (-2) + 1 或 7 = (-3) * (-3) + (-2)。

因此，7 rem (-3) = 1， 7 mod (-3) = (-2).

约数(因数)

约数（因数）：若 a∣b，则称 b 是 a 的倍数，a 是 b 的约数(因数)。

🌰 给定一个正整数 x(0<x<10^5), 从小到达输出 xx 的所有约数(因数)。

for (int i = 1; i <= x; i++) {
	if ( x % i == 0) {
		printf("%d ", i);
	}
}

质数与合数

设整数 p>1。如果 p 除了1和它自身外没有其他约数，那么称 p 为质数（或素数）。

若整数 a≠0,1 且 a 不是质数，则称 a 为合数。

整数的约数(因数)是质数，则该质数称为该整数的质因子。

质数与合数的简单性质：

• 大于 1 的整数 a 是合数，等价于 a 可以表示为整数 d 和 e（1<d,e<a）的乘积。
• 大于 1 的整数 a 一定可以表示为质数的乘积。
• 对于合数 a，一定存在素数 p≤a​ 使得 p∣a。
• 质数有无穷多个。

🌰 给定一个正整数 x(0<x<10^8), 判断其是否为质数。

// 函数返回值 0 为合数，1为质数
bool isPrime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if ( x % i == 0) {
			return 0;
		}
	}
	return 1;
}

互质(互素)

两个整数互素的定义：若 gcd⁡(a1,a2)=1，则称 a1​ 和 a2​ 互素。

多个整数互素的定义：若 gcd⁡(a1,…,ak)=1，则称 a1​,…,ak​ 互素。

多个整数互素，不一定两两互素。例如 6、10 和 15 互素，但是任意两个都不互素。

📜历年真题

单选题
1、10000 以内，与 10000 互质的正整数有（ ）个。

A. 2000
B. 4000
C. 6000
D. 8000

2、100以内最大的素数是( ).

A. 89
B. 97
C. 91
D. 93

3、干支纪年法是中国传统的纪年方法，由10个天干和12个地支组合成60个天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。 天干 =（公历年份）除以10所得余数 地支 =（公历年份）除以12所得余数 例如，今年是 2020 年，2020 除以 10 余数为 0，查表为"庚”；2020 除以 12，余数为 4，查表为“子” 所以今年是庚子年。 请问 1949 年的天干地支是( ).

A. 己酉

B. 己亥

C. 己丑

D. 己卯