洛谷P2833题解：扩展欧几里得算法求解线性方程整数解（详细步骤+代码实现）

一、题目解读

洛谷P2833题目要求求解线性方程 ax + by = c 在给定矩形区域 (x1, x2) × (y1, y2) 内的整数解数量。需处理系数 a, b 为0的特殊情况，并结合约束条件计算可行解的个数。问题核心在于将数学理论转化为编程实现，考验对扩展欧几里得算法的掌握。

二、解题思路

1. 核心算法：利用扩展欧几里得算法（EGCD）求解线性方程的通解形式，通过系数 a, b 的最大公约数 d 判断是否有解。

2. 边界处理：针对 a=0 或 b=0 的退化情况，分别计算单一变量的解范围。

3. 通解推导：通过特解 (x0, y0) 和系数关系，推导出通解 x = x0 + b*t, y = y0 - a*t，结合区间约束计算整数 t 的合法范围。

4. 优化细节：使用 ceil/floor 函数精确计算边界，避免浮点数误差。

三、解题步骤

1. 调用EGCD函数：定义 extended_gcd 递归计算 a, b 的GCD及系数 x, y，作为后续求解的基础。

2. 处理全0系数：若 a=b=0，方程恒成立时直接计算矩形区域面积；否则判断 c=0 是否成立。

3. 单系数0处理：当 a=0 或 b=0 时，将方程转化为单一变量求解，结合区间判断解的存在性。

4. 计算特解与调整：通过EGCD结果得到特解 (x0, y0)，根据系数符号调整方向。

5. 推导通解范围：利用通解公式计算 t 的上下界 t_low, t_high，确保解在矩形区域内。

6. 返回解数量：若 t 区间合法，计算区间长度并输出。

四、代码与注释

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

// 扩展欧几里得算法，求解 ax + by = gcd(a, b) 的系数
long long extended_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {  // 递归终止条件
        x = 1;
        y = 0;
        return a;  // GCD(a, 0) = a
    }
    long long d = extended_gcd(b, a % b, y, x);  // 递归调用
    y -= a / b * x;  // 系数回推公式
    return d;
}

// 计算线性方程在矩形区域内的整数解数量
long long count_solutions(long long a, long long b, long long c,
                         long long x1, long long x2,
                         long long y1, long long y2) {
    // 处理全0系数（方程恒成立或矛盾）
    if (a == 0 && b == 0) {
        return c == 0? (x2 - x1 + 1) * (y2 - y1 + 1) : 0;
    }
    
    // a=0 时方程变为 by = c
    if (a == 0) {
        if (b == 0) return 0;  // 矛盾情况
        if (c % b!= 0) return 0;  // 无解
        long long y = -c / b;  // 特解
        return (y >= y1 && y <= y2)? (x2 - x1 + 1) : 0;  // 计算x区间长度
    }
    
    // b=0 时同理
    if (b == 0) {
        if (a == 0) return 0;  // 矛盾
        if (c % a!= 0) return 0;
        long long x = -c / a;
        return (x >= x1 && x <= x2)? (y2 - y1 + 1) : 0;
    }

    // 计算GCD并判断是否有解
    long long x0, y0;
    long long d = extended_gcd(abs(a), abs(b), x0, y0);  // 确保a, b非负
    if (c % d!= 0) return 0;  // 无解条件

    // 调整特解符号（根据a, b实际符号）
    x0 *= (a < 0)? -1 : 1;
    y0 *= (b < 0)? -1 : 1;
    x0 *= -c / d;  // 计算特解 (x0, y0)
    y0 *= -c / d;
    a /= d;  // 归一化系数
    b /= d;
    
    // 通解公式 x = x0 + b*t, y = y0 - a*t
    long long t_low = max(ceil((x1 - x0) * 1.0 / b), ceil((y0 - y2) * 1.0 / a));  // t的下界
    long long t_high = min(floor((x2 - x0) * 1.0 / b), floor((y0 - y1) * 1.0 / a));  // t的上界
    return (t_high >= t_low)? (t_high - t_low + 1) : 0;  // 计算合法t的数量
}

int main() {
    ios::sync_with_stdio(false);  // 关闭同步加速输入
    cin.tie(0);
    long long a, b, c, x1, x2, y1, y2;
    cin >> a >> b >> c >> x1 >> x2 >> y1 >> y2;  // 输入参数
    cout << count_solutions(a, b, c, x1, x2, y1, y2) << endl;  // 输出解数量
    return 0;
}

五、总结

本文通过洛谷P2833题的代码实例，展示了扩展欧几里得算法在求解线性方程整数解问题中的完整流程。关键在于理解通解公式与区间约束的结合，以及针对系数特殊情况的分类讨论。代码中的边界处理和符号调整是避免错误的核心细节，建议读者在实际应用中结合数学推导验证算法的正确性。掌握此类算法不仅能提升竞赛解题能力，也为解决实际问题提供数学工具。