华理小男孩-姚远模板.pdf

根据给定文件的信息，我们可以梳理出一系列与计算机科学竞赛（如NOIP、ACM、NOI等）相关的算法和知识点。接下来将详细解释这些概念及其应用。 ### 数论 #### 指数降幂公式 指数降幂公式是用于简化较大指数在模意义下的计算的一种方法。具体来说： \[A^x \equiv A^{x \mod \phi(p) + \phi(p)} \mod p\] （当\(x \geq \phi(p)\)） 这里，\(\phi(p)\)是欧拉函数，表示小于等于\(p\)的正整数中与\(p\)互质的数的数量。这个公式的应用场景主要是在计算模意义下的大指数时简化计算过程，避免直接计算可能导致的数据溢出问题。 #### 威尔逊定理 威尔逊定理给出了一种判断素数的方法：如果\(p\)是素数，则有 \[(p-1)! \equiv -1 \mod p\] 即\(p-1\)的阶乘加1能够被\(p\)整除。这个定理可以用来验证一个数是否为素数。 #### 费马小定理 费马小定理也是判断素数的一个常用方法：如果\(p\)是素数且\(a\)不是\(p\)的倍数，则有 \[a^p \equiv a \mod p\] 更一般地，若\(a\)与\(p\)互质，则有 \[a^{p-1} \equiv 1 \mod p\] 这同样提供了一个简单而有效的方式来检测素数。 #### 欧拉定理 欧拉定理是对费马小定理的一种推广，它适用于所有正整数： \[a^{\phi(n)} \equiv 1 \mod n\] （当\(a\)与\(n\)互质时） 其中\(\phi(n)\)是欧拉函数，表示小于等于\(n\)的正整数中与\(n\)互质的数的数量。这个定理广泛应用于密码学等领域。 #### 质数表 质数表是指通过筛法预先计算一定范围内的所有质数，并存储起来供后续使用。常见的筛法包括埃拉托斯特尼筛法等。例如，以下是一个简单的质数筛法实现： ```cpp const int N = 1000000 + 9; bool p[N]; int a[N]; int main() { int n; cin >> n; int cnt = 0; for (int i = 0; i <= n; i++) p[i] = true; for (int i = 2; i <= n; i++) { if (p[i]) a[cnt++] = i; for (int j = 0; j < cnt; j++) { if (i * a[j] > n) break; p[i * a[j]] = false; if (i % a[j] == 0) break; } } cout << cnt << endl; } ``` 这段代码使用了埃拉托斯特尼筛法来找出小于等于\(n\)的所有质数。 #### 素数函数 素数函数通常指的是与素数相关的各种函数，例如计算某个区间内素数的数量等。以下是一个简单的例子，展示了如何定义素数函数并计算特定值。 ```cpp #include typedef long long ll; using namespace std; ll f[340000], g[340000], n; // 这里可以添加计算素数函数的具体逻辑 ``` 以上是关于数论部分的一些基本知识点和算法介绍。接下来将探讨概率论、矩阵运算、图论等方面的内容。 --- 以上内容仅为数论部分的总结，接下来将逐步介绍概率论、数学、图论、计算几何、数据结构以及字符串处理等相关知识点。这些知识点对于参加NOIP、ACM和NOI等计算机科学竞赛的学生来说非常重要，有助于他们在比赛中取得好成绩。