C++ Fermat‘s little theorem费马小定理寻找模逆实现算法(附完整源码)

### 费马小定理的C++实现 费马小定理指出，如果 \( p \) 是一个素数，且整数 \( a \) 不被 \( p \) 整除，则有如下关系成立：\[ a^{p-1} \equiv 1 \ (\text{mod}\ p) \]。利用这一性质，可以通过快速幂算法高效地验证该结论。 以下是一个完整的C++程序实现： ```cpp #include <iostream> using namespace std; // 快速幂取模函数 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; // 右移一位相当于除以2 } return result; } // 判断是否满足费马小定理 bool fermat_little_theorem(long long a, long long p) { if (p <= 1 || a % p == 0) return false; // 排除非素数或a能被p整除的情况 return fast_pow(a, p - 1, p) == 1; // 计算a^(p-1) % p 是否等于1 } int main() { long long a, p; cout << "请输入a和p：" << endl; cin >> a >> p; if (fermat_little_theorem(a, p)) { cout << "满足费马小定理" << endl; } else { cout << "不满足费马小定理" << endl; } return 0; } ``` 上述代码中定义了一个`fast_pow`函数用于执行快速幂运算[^1]，并通过它来检验给定的\(a\)和\(p\)是否符合费马小定理的要求[^2]。注意，在实际应用中需考虑边界条件以及可能存在的伪素数问题[^3]。 ---