初等数论中的基础概念

近3年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

取模和取余
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∣ba\mid ba∣b，则称 bbb 是 aaa 的倍数，aaa 是 bbb 的约数(因数)。

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

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

质数与合数

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

若整数 a≠0,1 且 a 不是质数，则称 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;
}

Warning!
质数判断中的易错点👇👇👇

互质(互素)

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

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

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

📜历年真题

题解

这是一个简单的容斥原理，首先如果一个数a与10000有大于1的公因数x，那么x必然可以被质因数分解为一些质数的乘积，也就是说只有当a和10000有至少一个相同的质因子的时候，他们之间才会有大于1的公因数。

之后，我们可以对10000分解质因数，分解出来只有2和5。与10000互质的数的个数=数的总数-不与10000互质的数的个数

再考虑1-10000有多少个数里面有2这个质因子，显然有10000/2=5000个（可以举几个例子如1-15,1-20来理解），以此类推，有10000/5=2000个数里面有5这个质因子。

但是答案并不是10000-2000-5000=3000，为什么？因为像10、20这样既有2这个质因子也有5这个质因子的数既被2统计到又被5统计到了。也就是有10这个因子的数被统计到了两次，加上这些数的个数10000/10=1000，就是最后的答案4000

试除法判断质数和分解质因数

近3年CSPJ考察情况：

	题号	题型	分值
2020	第19题	完善程序	15分
2022	第19题	完善程序	15分

难易度：中等

2023年备考建议

试除法和质因数分解是一个必须必须要掌握的知识点。因为其算法想法简单，但是考察确很多。究其原因，数论的内容一旦考察深了，就过难，容易没有区分度，比如2021年的筛法考察，那个题目绝大多数考生都是干瞪眼，题是很好，区分度不足。而质因数分解的难度就刚好，而且还可以和其他各种算法做结合。务必会写。

朴素试除法

判断一个数x是否是质数（很多时候称为素性测试），最简单的方法是试除法。试除，就是用2,3,…,x−1这些数字尝试整除x。只要其中有一个数能整除x，就说明x是合数，反之是质数。

// 写成函数形式的试除法，若为合数函数返回0，为质数函数返回1
bool isPrime(int x) {
    if (x < 2) return 0;
    for (int i = 2; i < x; i++) {
        if (x % i == 0) return 0;
    }
    return 1;
}

试除法(优化后)

程序的过程，就像在数轴x−1的位置建了一堵墙，i从2开始不断右移到这堵“墙”，每次都要进行 x%i的计算，若结果为0，说明i是x的因数，x是合数。

// 优化后的试除法
bool isPrime(long long x) {
    if (x < 2) return 0;
    // 将 i < x 优化为 i * i <= x
    for (long long i = 2; i * i <= x; i++) {
        if (x % i == 0) return 0;
    }
    return 1;
}

分解质因数

给定一个正整数，找到它的所有因数。

vector <int> breakdown(int x) {
    vector <int> res;
    for (int i = 1; i <= x; i++) {
        if (x % i == 0) {
            while (x % i == 0) x /= i;
            res.push_back(i);
        }
    }
    if (x != 1) res.push_back(x);
    return res;
}

历年真题试除法求质数

(略)

DAY2-质数判断和质因数分解