数论基础：取模运算与质数判断

"这篇资料主要介绍了数论的基础知识，包括取模运算、试除法、质数判断、唯一分解定理、求约数个数和约数和的方法，以及筛法找质数的基本思想。" 在数论这个数学分支中，有几个关键概念和技术： 1. **取模运算**：取模运算 `%` 在计算机科学中广泛使用，特别是在处理整数除法时。对于负数取模，一般遵循规则 `a % b = |a| % |b|`，并保持结果与 `a` 的符号一致。在计算模 `p` 的情况下，可以使用 `(ans % p + p) % p` 来将结果调整到 `0` 到 `p-1` 的范围内。快速幂算法 `qmi` 可以高效计算 `a^k` 对 `p` 取模的结果，其复杂度为 `O(log k)`。 2. **试除法**：试除法用于找出一个数的所有约数。例如，对于整数 `n`，通过循环 `i` 从 `1` 到 `√n`，检查 `n` 是否能被 `i` 整除。若能，则 `i` 和 `n/i` 都是 `n` 的约数。此方法可用于求解约数个数和约数和。例如，10000以内的因子数最多的是128个，而100000000以内因子数最多的不超过800个。 3. **判断质数**：`isPrime` 函数通过试除法判断一个数是否为质数。从 `2` 开始，直到 `√n`，如果 `n` 能被其中任何数整除，则 `n` 不是质数；反之则是质数。 4. **唯一分解定理**：每个正整数 `n` 可以唯一地表示为若干个质数的乘积，即 `n = p1^c1 * p2^c2 * ... * pk^ck`。例如，12可以表示为 `2^2 * 3^1`。`divide` 函数可以用来分解一个数为质因数的乘积形式。 5. **约数性质**：约数个数可以通过质因数分解来计算，公式为 `(c1+1) * (c2+1) * (c3+1) * ... * (ck+1)`，其中 `ci` 是质因数 `pi` 的指数。约数和可以通过类似的方法计算，涉及到每个质因数的幂次的组合。 6. **筛法**：筛法是一种寻找质数的有效方法，如朴素筛法，通过一个布尔数组 `vis[N]` 记录每个数是否是质数，以及一个数组 `pri[cnt]` 存储质数。从2开始，标记所有2的倍数为非质数，然后继续查找下一个未标记的数，重复此过程，直到找到所有小于或等于给定上限 `n` 的质数。 这些基础知识在解决数论问题、编码竞赛以及密码学等领域中都至关重要，理解并掌握它们对提升编程能力很有帮助。