费马小定理c++

费马小定理是一个数论定理，它可以用来快速求解模意义下的乘法逆元。

假设有一个素数 p 和一个整数 a，且 a 和 p 互质（即 gcd(a, p) = 1），那么根据费马小定理，有：

$a^{p-1} \equiv 1 \pmod p$

因此，我们可以通过下面的公式来计算 a 在模 p 意义下的乘法逆元：

$a^{-1} \equiv a^{p-2} \pmod p$

注意，这个公式只在 a 和 p 互质时成立。

下面是一个使用费马小定理计算乘法逆元的 C++ 代码示例：

int modpow(int base, int exp, int modulus) {
    base %= modulus;
    int result = 1;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % modulus;
        base = (base * base) % modulus;
        exp >>= 1;
    }
    return result;
}

int modinv(int a, int p) {
    return modpow(a, p-2, p);
}

其中，`modpow` 函数用来计算模幂，`modinv` 函数用来计算乘法逆元。

相关问题

题目描述 该题为「Fermat-1」的 Special Judge。 很有实力的 zyh 又出了一道「费马与定理」。 给定两个正整数 d,n，满足 d,n≤2.5×10 5 ，问是否有 d 是n!+1 的次小约数。 输入格式 本题多测。 第一行，一个正整数 T，表示数据组数。 随后输入 T 组数据。对于每组数据，输入两个正整数d,n，其意义如题目中所描述。 输出格式 对于每组数据，若 d 是 n!+1 的次小约数，则输出 Yes；否则输出 No。（c++代码）

对于每组数据，我们需要判断是否存在一个数 d，它是 n!+1 的次小约数。我们可以通过计算 n!+1 的所有约数，并找出其中次小的约数来判断。

首先，我们可以使用一个循环来计算 n! 的值。然后，我们可以使用另一个循环来遍历所有可能的约数，并检查它是否满足条件。

以下是实现该功能的 C++ 代码：

#include <iostream>

using namespace std;

// 计算 n! 的值
long long factorial(int n) {
    long long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

// 判断 d 是否是 n!+1 的次小约数
bool isSecondSmallestDivisor(int d, int n) {
    long long num = factorial(n) + 1;
    for (int i = 2; i <= num / 2; i++) {
        if (num % i == 0) {
            if (d == i) {
                return true;
            }
            break;
        }
    }
    return false;
}

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        int d, n;
        cin >> d >> n;
        
        if (isSecondSmallestDivisor(d, n)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    
    return 0;
}

请注意，上述代码使用了 long long 类型来存储 n! 的结果，以避免溢出。

c++费马素性测试

费马素性测试是一种快速判断一个数是否为质数的方法，它基于费马小定理，即对于所有的质数p和整数a，都有a^p ≡ a (mod p)。下面是一个C++实现的费马素性测试：

#include <iostream>
#include <cmath>
using namespace std;

bool is_prime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    int a = rand() % (n - 2) + 2;
    int p = n - 1;
    while (p % 2 == 0) {
        if (pow(a, p / 2) % n == n - 1) return true;
        p /= 2;
    }
    int res = pow(a, p) % n;
    return res == 1 || res == n - 1;
}

int main() {
    int n;
    cin >> n;
    if (is_prime(n)) {
        cout << n << " is a prime number." << endl;
    } else {
        cout << n << " is not a prime number." << endl;
    }
    return 0;
}

该函数先判断n是否小于2或为偶数，如果是则直接返回false。然后随机取一个整数a，如果a^(n-1) ≢ 1 (mod n)，则n一定不是质数，返回false。否则继续对n-1进行因式分解，如果存在一个因子p使得a^(p/2) ≡ -1 (mod n)，则n可能是质数，返回true。否则继续取一个随机数a，重复上述步骤，直到判断n为质数或执行一定次数后退出。