C++模运算，快速幂取模，模线性方程

在C++中，我们可以使用模运算（取模）来确保结果在给定模数下的范围内。C++中的模运算使用取模操作符（%）进行计算。

快速幂取模是一种高效计算指数幂的方法，同时对结果进行模运算，以避免整数溢出。以下是一个示例函数，演示如何使用快速幂取模计算一个数的幂。

#include <iostream>

// 快速幂取模函数
int powerMod(int base, int exponent, int modulus) {
    int result = 1;
    base %= modulus;

    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % modulus;
        }

        base = (base * base) % modulus;
        exponent /= 2;
    }

    return result;
}

int main() {
    int base = 3;
    int exponent = 5;
    int modulus = 1000000007;

    int result = powerMod(base, exponent, modulus);
    std::cout << base << "^" << exponent << " % " << modulus << " = " << result << std::endl;

    return 0;
}

在上述示例中，我们使用powerMod函数计算3的5次幂对1000000007取模的结果。这将输出结果 3^5 % 1000000007 = 243。

模线性方程是一种在模运算下求解线性方程的方法。一个模线性方程的一般形式为：

ax ≡ b (mod m)

其中，a、b和m是已知的整数，x是未知的整数。为了求解这个方程，我们可以使用扩展欧几里得算法（Extended Euclidean Algorithm）。

以下是一个示例函数，演示如何使用扩展欧几里得算法解决模线性方程：

#include <iostream>

// 扩展欧几里得算法
int extendedGCD(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    int x1, y1;
    int gcd = extendedGCD(b, a % b, x1, y1);

    x = y1;
    y = x1 - (a / b) * y1;

    return gcd;
}

// 模线性方程求解函数
void solveLinearCongruence(int a, int b, int m) {
    int x, y;
    int gcd = extendedGCD(a, m, x, y);

    if (b % gcd == 0) {
        int x0 = (x * (b / gcd)) % m;
        for (int i = 0; i < gcd; i++) {
            int solution = (x0 + i * (m / gcd)) % m;
            std::cout << "x ≡ " << solution << " (mod " << m << ")" << std::endl;
        }
    } else {
        std::cout << "No solution exists." << std::endl;
    }
}

int main() {
    int a = 7;
    int b = 3;
    int m = 10;

    solveLinearCongruence(a, b, m);

    return 0;
}

在上述示例中，我们使用solveLinearCongruence函数解决模线性方程 7x ≡ 3 (mod 10)。该方程的解为 x ≡ 7 (mod 10)。

请注意，这些示例只是演示了如何在C++中使用模运算、快速幂取模和模线性方程的基本方法。实际应用中，可能需要处理更大的数值，以及处理溢出、负数和其他特殊情况的边界条件。