使用C++找到模方程的解的数量

1. 什么是模方程

在数学中，模方程是指形如：ax ≡ b (mod n) 的方程，其中a、b和n都是整数，x是未知数。

mod是一个缩写词，代表模(modulus)。ax ≡ b (mod n)读作：ax除以n的余数等于b除以n的余数。

2. 解决模方程的方法

2.1 一般解法

一般来说，要解决ax ≡ b (mod n)这个模方程，可以使用以下的步骤：

Step 1: 将方程转换为ax - b = nk的形式

Step 2: 求ax - b和n的最大公约数gcd(a, n)

Step 3: 如果gcd(a, n)不能整除nk，说明方程无解

Step 4: 如果gcd(a, n)能整除nk，说明存在解

Step 5: 求x0(一组特解)，用xk = x0 + k(n / gcd(a, n))来求出所有解

2.2 快速解法

快速解法指的是当n是质数的时候，使用逆元的方式来求解模方程。使用逆元的方式可以省略掉计算除法的过程，从而加快计算的速度。

如果n是质数，那么我们可以使用费马小定理求解逆元，这样就可以避免计算除法。

我们可以将模方程ax ≡ b (mod n)改写为ax = b + ny，其中y是整数。然后我们将两边同时除以a，得到x = b * a^-1 + ny * a^-1，其中a^-1是a在模n意义下的逆元。

由于n是质数，所以费马小定理告诉我们a^(n-1) ≡ 1 (mod n)，所以a * a^-1 ≡ 1 (mod n)。因此，我们可以求出a在模n意义下的逆元，即a^-1 = a^(n-2) (mod n)。将a^-1代入上面的公式，就可以求出x的值了。

3. C++代码实现

3.1 一般解法

#include <iostream>
using namespace std;
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
int main() {
    int a, b, n;
    cin >> a >> b >> n;
    int d = gcd(a, n);
    if (b % d != 0) {
        cout << "No solution." << endl;
    } else {
        int x0 = ((b / d) * (a / d) % (n / d) + (n / d)) % (n / d);
        for (int i = 0; i < d; i++) {
            cout << (x0 + i * (n / d)) % n << " ";
        }
        cout << endl;
    }
    return 0;
}

3.2 快速解法

#include <iostream>
using namespace std;
int power(int a, int b, int n) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = (long long)ans * a % n;
        a = (long long)a * a % n;
        b >>= 1;
    }
    return ans;
}
int main() {
    int a, b, n;
    cin >> a >> b >> n;
    int inv = power(a, n - 2, n);
    int ans = (long long)b * inv % n;
    cout << ans << endl;
    return 0;
}

4. 总结

模方程是一种常见的数学问题，我们可以使用一般解法或快速解法来求解模方程。一般解法适用于所有的情况，但对于大数的情况，计算过程会比较耗费时间。快速解法适用于当n是质数的情况，计算过程比较快速，但需要使用逆元的方式来求解。

在实际应用当中，我们通常会使用快速解法来处理模方程，尤其是在需要高效计算的场景下。因此，学会使用逆元的计算方法是非常重要的。