C12第2章模方程

admin

1. 扩展欧几里得算法
扩展欧几里得算法是求解模方程的基础，它不仅能计算两个数的最大公约数，还能找到满足方程 ax + by = gcd(a, b) 的整数解 x 和 y。这个算法是递归实现的，通过回溯计算出最终的解。

2. 一元线性同余方程
一元线性同余方程的形式为 ax ≡ b (mod m)，求解该方程的步骤：
使用扩展欧几里得算法计算 gcd(a, m)
若 b 不能被 gcd(a, m) 整除，则方程无解
否则，先求出一个特解，再根据 gcd(a, m) 的值确定解的数量和通解形式
示例 1 中，方程 3x ≡ 6 (mod 9) 的解为 x ≡ 2, 5, 8 (mod 9)，共 3 个解，因为 gcd(3, 9) = 3。

3. 中国剩余定理
中国剩余定理用于求解模数两两互质的同余方程组，形式为：
plaintext
x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₙ (mod mₙ)
其中所有 mᵢ 两两互质。求解过程是逐步合并方程，最终得到一个解 x ≡ c (mod M)，其中 M 是所有 mᵢ 的乘积。
示例 2 中，方程组的解为 x ≡ 23 (mod 105)，因为 105 是 3、5、7 的乘积，且 23 满足所有三个同余式。

4. 模数不互质的同余方程组
当模数不互质时，不能直接应用中国剩余定理，需要更一般的解法：
逐步合并两个方程，检查是否有解
若有解，则得到一个新的同余方程
重复此过程直到所有方程合并完成
示例 3 中，方程组 x ≡ 2 (mod 4) 和 x ≡ 4 (mod 6) 的解为 x ≡ 10 (mod 12)，因为 10 同时满足两个同余式。
这些算法在密码学、数论和计算机科学中有广泛应用，例如在 RSA 加密、哈希函数设计和伪随机数生成等领域。

[C++] 纯文本查看 复制代码

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

/**
 * 扩展欧几里得算法
 * 求解 ax + by = gcd(a, b)
 * @param a 方程系数
 * @param b 方程系数
 * @param x 解x的引用
 * @param y 解y的引用
 * @return a和b的最大公约数
 */
long long extendedGcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long g = extendedGcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

/**
 * 求解一元线性同余方程 ax ≡ b (mod m)
 * 方程有解的充要条件是 gcd(a, m) 能整除 b
 * @param a 系数
 * @param b 常数项
 * @param m 模数
 * @param x 解的引用（若有解）
 * @return 解的数量，0表示无解，否则返回解的数量（gcd(a,m)）
 */
int solveLinearCongruence(long long a, long long b, long long m, long long& x) {
    long long g, x0, y0;
    g = extendedGcd(a, m, x0, y0);  // 求解 ax0 + my0 = g
    
    // 检查是否有解：b必须能被g整除
    if (b % g != 0) {
        return 0;  // 无解
    }
    
    // 计算一个特解
    x0 = x0 * (b / g) % m;
    // 保证解为正数
    if (x0 < 0) {
        x0 += m;
    }
    x = x0;
    
    // 解的数量为g，通解为 x0 + k*(m/g)，其中k=0,1,...,g-1
    return g;
}

/**
 * 中国剩余定理（求解同余方程组）
 * 解形如：
 * x ≡ a1 (mod m1)
 * x ≡ a2 (mod m2)
 * ...
 * x ≡ an (mod mn)
 * 要求所有mi两两互质
 * @param congruences 同余式列表，每个元素为(a_i, m_i)
 * @param x 解的引用
 * @param mod 解的模数（所有m_i的乘积）
 * @return 是否有解
 */
bool chineseRemainderTheorem(const vector<pair<long long, long long>>& congruences, 
                           long long& x, long long& mod) {
    x = 0;
    mod = 1;
    
    for (const auto& [a, m] : congruences) {
        // 当前方程：x ≡ a (mod m)
        // 合并方程：x = x0 + k*mod，代入得 x0 + k*mod ≡ a (mod m)
        // 即 k*mod ≡ (a - x0) (mod m)
        
        long long g, k, tmp;
        long long c = (a - x) % m;
        if (c < 0) c += m;  // 确保c为正数
        
        g = extendedGcd(mod, m, k, tmp);  // 求解 k*mod + tmp*m = g
        
        // 检查是否有解
        if (c % g != 0) {
            return false;  // 无解
        }
        
        // 计算k的一个解
        long long lcm = mod / g * m;  // 最小公倍数
        k = k * (c / g) % (m / g);
        if (k < 0) k += m / g;
        
        // 更新x和mod
        x += k * mod;
        mod = lcm;
        x %= mod;  // 保持x在[0, mod)范围内
    }
    
    return true;
}

/**
 * 求解模数不互质的同余方程组
 * @param congruences 同余式列表，每个元素为(a_i, m_i)
 * @param x 解的引用
 * @param mod 解的模数（所有m_i的最小公倍数的因子）
 * @return 是否有解
 */
bool solveCongruenceSystem(const vector<pair<long long, long long>>& congruences,
                          long long& x, long long& mod) {
    x = 0;
    mod = 1;
    
    for (const auto& [a, m] : congruences) {
        // 合并方程：x ≡ x0 (mod mod) 和 x ≡ a (mod m)
        long long g, tmp, k;
        long long c = (a - x) % m;
        if (c < 0) c += m;
        
        g = extendedGcd(mod, m, k, tmp);
        
        // 检查是否有解
        if (c % g != 0) {
            return false;
        }
        
        // 计算新的解和模数
        long long new_mod = mod / g * m;
        k = k * (c / g) % (m / g);
        if (k < 0) k += m / g;
        
        x += k * mod;
        mod = new_mod;
        x %= mod;
    }
    
    return true;
}

int main() {
    // 示例1：求解一元线性同余方程
    cout << "=== 示例1：一元线性同余方程 ===" << endl;
    long long a = 3, b = 6, m = 9;
    long long x;
    int solutions = solveLinearCongruence(a, b, m, x);
    cout << "求解方程: " << a << "x ≡ " << b << " (mod " << m << ")" << endl;
    if (solutions == 0) {
        cout << "方程无解" << endl;
    } else {
        cout << "方程有 " << solutions << " 个解" << endl;
        long long step = m / solutions;
        for (int i = 0; i < solutions; ++i) {
            long long sol = (x + i * step) % m;
            cout << "解 " << i + 1 << ": x ≡ " << sol << " (mod " << m << ")" << endl;
        }
    }
    cout << endl;
    
    // 示例2：中国剩余定理（模数互质）
    cout << "=== 示例2：中国剩余定理（模数互质） ===" << endl;
    vector<pair<long long, long long>> crt_congs = {
        {2, 3},   // x ≡ 2 (mod 3)
        {3, 5},   // x ≡ 3 (mod 5)
        {2, 7}    // x ≡ 2 (mod 7)
    };
    long long crt_x, crt_mod;
    bool crt_has_solution = chineseRemainderTheorem(crt_congs, crt_x, crt_mod);
    if (crt_has_solution) {
        cout << "方程组的解为: x ≡ " << crt_x << " (mod " << crt_mod << ")" << endl;
        // 验证解
        for (const auto& [a, m] : crt_congs) {
            cout << "验证: " << crt_x << " mod " << m << " = " << crt_x % m << " (应等于 " << a << ")" << endl;
        }
    } else {
        cout << "方程组无解" << endl;
    }
    cout << endl;
    
    // 示例3：求解模数不互质的同余方程组
    cout << "=== 示例3：模数不互质的同余方程组 ===" << endl;
    vector<pair<long long, long long>> sys_congs = {
        {2, 4},   // x ≡ 2 (mod 4)
        {4, 6}    // x ≡ 4 (mod 6)
    };
    long long sys_x, sys_mod;
    bool sys_has_solution = solveCongruenceSystem(sys_congs, sys_x, sys_mod);
    if (sys_has_solution) {
        cout << "方程组的解为: x ≡ " << sys_x << " (mod " << sys_mod << ")" << endl;
        // 验证解
        for (const auto& [a, m] : sys_congs) {
            cout << "验证: " << sys_x << " mod " << m << " = " << sys_x % m << " (应等于 " << a << ")" << endl;
        }
    } else {
        cout << "方程组无解" << endl;
    }
    
    return 0;
}

admin

有两种砝码，一种是 a 克的，一种是 b 克的，还有一个天平，天平左右均可放砝码，现要称重 d 克的物品，要求使用的砝码总量最少，如果有多种方案，则需要总重量最小的方案。


核心原理
天平称重问题的本质是求解线性方程 a*x + b*y = d，其中：
x 和 y 为整数（可正可负）
正数表示砝码放在物品的对侧（与物品平衡）
负数表示砝码放在物品的同侧（与物品一起平衡对侧砝码）
方程有解的充要条件是：d 必须是 a 和 b 的最大公约数（gcd）的倍数。

代码步骤
扩展欧几里得算法：求解 a*x + b*y = gcd(a,b)，为后续求特解奠定基础。
解的存在性判断：若 d 不能被 gcd(a,b) 整除，则无解。
方程化简：将原方程化为 a'*x + b'*y = d'（其中 a'=a/gcd，b'=b/gcd，d'=d/gcd），此时 a' 和 b' 互质。
特解与通解：通过扩展欧几里得的解得到特解，再推导通解公式 x = x0 + k*b'，y = y0 - k*a'（k 为整数）。
最优解筛选：在通解中寻找 |x| + |y| 最小（数量最少）的解，若数量相同则选择 |x|*a + |y|*b 最小（总重量最小）的解。


示例说明
以 a=3、b=5、d=7 为例：
方程为 3x + 5y = 7
特解为 x=14，y=-7，通解为 x=14+5k，y=-7-3k
当 k=-3 时，x=-1，y=2，满足 3*(-1) + 5*2 = 7
此时使用 1 个 a 砝码（同侧）和 2 个 b 砝码（对侧），总数量 3，总重量 13，为最优解

[C++] 纯文本查看 复制代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

/**
 * 扩展欧几里得算法
 * 求解 ax + by = gcd(a, b)，返回最大公约数gcd(a,b)，并通过引用返回x和y
 */
long long extendedGcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long g = extendedGcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// 存储解决方案的结构体
struct Solution {
    long long x;       // a砝码数量（正：放对侧，负：放同侧）
    long long y;       // b砝码数量（正：放对侧，负：放同侧）
    long long count;   // 总数量（|x| + |y|）
    long long weight;  // 总重量（|x|*a + |y|*b）
    
    // 构造函数：计算数量和重量
    Solution(long long x_, long long y_, long long a, long long b) 
        : x(x_), y(y_) {
        count = abs(x) + abs(y);
        weight = abs(x) * a + abs(y) * b;
    }
};

int main() {
    long long a, b, d;
    cout << "请输入两个砝码重量a、b和物品重量d：";
    cin >> a >> b >> d;

    long long x0, y0;  // 扩展欧几里得算法的解
    long long g = extendedGcd(a, b, x0, y0);  // 计算gcd(a,b)

    // 检查是否有解：d必须是gcd(a,b)的倍数
    if (d % g != 0) {
        cout << "无法用给定砝码称重" << endl;
        return 0;
    }

    // 化简方程：a'x + b'y = d'（其中a'=a/g, b'=b/g, d'=d/g，此时a'和b'互质）
    long long a_prime = a / g;
    long long b_prime = b / g;
    long long d_prime = d / g;

    // 计算原方程的一个特解（扩展欧几里得解乘以d'）
    x0 *= d_prime;
    y0 *= d_prime;

    // 通解公式：x = x0 + k*b'，y = y0 - k*a'（k为整数）
    // 生成候选k值（围绕最优解附近的整数）
    vector<long long> candidates;

    // 基于x=0时的k值（让x尽可能接近0）
    if (b_prime != 0) {
        long long k1 = (-x0) / b_prime;  // 近似k值
        for (long long k = k1 - 2; k <= k1 + 2; ++k) {
            candidates.push_back(k);
        }
    }

    // 基于y=0时的k值（让y尽可能接近0）
    if (a_prime != 0) {
        long long k2 = y0 / a_prime;  // 近似k值
        for (long long k = k2 - 2; k <= k2 + 2; ++k) {
            candidates.push_back(k);
        }
    }

    // 补充几个可能的k值，避免遗漏最优解
    candidates.push_back(0);
    candidates.push_back(1);
    candidates.push_back(-1);

    // 去重候选k值
    sort(candidates.begin(), candidates.end());
    auto last = unique(candidates.begin(), candidates.end());
    candidates.erase(last, candidates.end());

    // 验证每个候选k值，收集有效解
    vector<Solution> solutions;
    for (long long k : candidates) {
        long long x = x0 + k * b_prime;  // 计算当前k对应的x
        long long y = y0 - k * a_prime;  // 计算当前k对应的y

        // 验证解是否正确（防止计算误差）
        if (a * x + b * y == d) {
            solutions.emplace_back(x, y, a, b);
        }
    }

    // 理论上不会出现无解（前面已判断有解），但做个保险
    if (solutions.empty()) {
        cout << "无法用给定砝码称重" << endl;
        return 0;
    }

    // 筛选最优解：先按数量最少，再按总重量最小
    Solution best = solutions[0];
    for (const auto& sol : solutions) {
        if (sol.count < best.count) {
            best = sol;
        } else if (sol.count == best.count && sol.weight < best.weight) {
            best = sol;
        }
    }

    // 输出结果
    cout << "\n最优称重方案：" << endl;
    cout << "a砝码使用数量（正：放对侧，负：放同侧）：" << best.x << endl;
    cout << "b砝码使用数量（正：放对侧，负：放同侧）：" << best.y << endl;
    cout << "使用砝码总数量：" << best.count << endl;
    cout << "使用砝码总重量：" << best.weight << endl;

    // 解释称重原理
    cout << "\n称重原理：";
    if (best.x >= 0 && best.y >= 0) {
        cout << "物品 + 0 = " << best.x << "个a砝码 + " << best.y << "个b砝码";
    } else if (best.x < 0 && best.y >= 0) {
        cout << "物品 + " << -best.x << "个a砝码 = " << best.y << "个b砝码";
    } else if (best.x >= 0 && best.y < 0) {
        cout << "物品 + " << -best.y << "个b砝码 = " << best.x << "个a砝码";
    } else {
        cout << "物品 + " << -best.x << "个a砝码 + " << -best.y << "个b砝码 = 0";
    }
    cout << "（等式两边平衡）" << endl;

    return 0;
}