c++费马小定理

### 费马小定理及其在C++中的实现 费马小定理是一个重要的数论工具，在模运算中有广泛应用。它指出如果 \( p \) 是一个素数，而整数 \( a \) 不被 \( p \) 整除，则有： \[ a^{p-1} \equiv 1 \ (\text{mod}\ p) \] 由此可以推导出 \( a^{-1} \equiv a^{p-2} \ (\text{mod}\ p) \)，这使得我们可以通过快速幂算法高效地计算乘法逆元。 以下是基于费马小定理的 C++ 示例代码用于计算模意义下的乘法逆元[^1]： ```cpp #include <iostream> using namespace std; // 快速幂函数：计算 (base^exp) % mod 的结果 long long fast_pow(long long base, long long exp, long long mod) { long long result = 1; while (exp > 0) { if (exp & 1) { // 如果指数当前位为1 result = (__int128(result) * base) % mod; // 防止溢出 } base = (__int128(base) * base) % mod; // 平方并取模 exp >>= 1; // 右移一位 } return result; } // 计算 a 关于模 p 的乘法逆元 long long inverse_modulo(long long a, long long p) { return fast_pow(a, p - 2, p); // 使用费马小定理 } int main() { long long a, p; cout << "Enter the value of 'a' and prime number 'p': "; cin >> a >> p; if (a >= p || __gcd((int)a, (int)p) != 1) { cout << "Inverse does not exist or input is invalid." << endl; } else { long long inv = inverse_modulo(a, p); cout << "The modular multiplicative inverse of " << a << " modulo " << p << " is: " << inv << endl; } return 0; } ``` 上述代码实现了两个主要功能： 1. **快速幂**：`fast_pow` 函数利用二分的思想加速幂次计算。 2. **乘法逆元**：调用 `inverse_modulo` 来返回给定数值关于某个素数模的意义下的逆元[^2]。 #### 应用场景分析 费马小定理的应用广泛存在于多个领域，特别是在涉及模运算的情况下。例如： - 密码学中 RSA 加密系统的公钥和私钥生成过程需要用到大质数上的模逆元操作。 - 组合计数问题可能需要频繁进行分数形式的结果简化，此时也需要借助模逆元来完成除法模拟[^4]。 另外需要注意的是，当题目规模较大或者精度要求较高时，应考虑数据类型的选取以及防止中间变量越界等问题。以上程序采用了 `__int128` 类型以规避部分潜在风险。