C++模板集：包括GCD快速幂与欧几里得算法实现

本资源是一份关于C++编程的详细教程，重点涵盖了一些核心算法和数据结构的实现，包括模板编程技术在其中的应用。以下是部分内容的详细解析： 1. **最大公约数（GCD）和快速幂算法**： - **递归版本**：`int gcd(int a, int b)` 函数采用欧几里得算法（Euclidean Algorithm），通过递归地计算两个数的余数来求最大公约数。当`b`为0时，返回`a`作为结果。 - **非递归版本**：`ll PowerMod(ll a, ll n, ll m = mod)` 和 `llPowerMod(ll a, int n, ll c = 1)` 分别是快速幂算法的实现，用于求解`a`的`n`次方模`m`。非递归版本通过位操作将`n`不断除以2，同时更新结果和中间变量。 2. **扩展欧几里得算法（Extended Euclidean Algorithm）**：`llexgcd(ll a, ll b, ll& x, ll& y)` 是一个通用的求解扩展欧几里得算法的函数，用于求解两个整数的最大公约数及其贝祖等式（Bézout's identity）的系数`x`和`y`。 3. **阶乘和逆元计算**： - **初始化函数**：`void init()` 和 `void init(int n)` 分别用于计算一系列整数的阶乘（`fact[]`）和它们的逆元（`finv[]`）。`init()`函数计算`N`范围内的逆元，而`init(int n)`则限制在`n`以内。 - **逆元的计算**：逆元`inv[]`是阶乘数组`fact[]`的逆元，对于每个`i`，`inv[i]`是`mod`除以`i`的逆元。 4. **素数相关算法**： - **线性筛法**：这是一种用于找到一定范围内所有素数的高效算法，同时计算出每个数的最小素因子。它在处理素数分解时非常有用。 - **Miller-Rabin素数检验**：这是一种概率性素数测试，通过重复随机化过程来判断一个数是否为素数，对于大型数值非常实用。 - **质因数分解**：文档中提到的这些函数可能涉及质因数分解的步骤，如使用上述的素数算法辅助分解。 这份文档是C++编程者的宝典，涵盖了基础数学运算、高效率算法以及与C++模板相关的实现技巧，对提升编程技能和解决实际问题有很高的参考价值。通过学习和实践这些代码，读者可以深入理解C++模板在高效算法中的应用，并将其运用到自己的项目中。