洛谷P2833题解：线性方程整数解的计数方法

一、问题分析

题目要求计算线性方程ax + by + c = 0在给定x和y范围内的整数解个数。这是一个典型的数论问题，需要运用扩展欧几里得算法和数学推导。

二、算法核心思路

1. 扩展欧几里得算法：求解ax + by = gcd(a,b)的特解

2. 解的存在性判断：根据c是否能被gcd(a,b)整除

3. 通解公式推导：利用特解和参数t表示所有解

4. 范围约束处理：计算参数t的有效范围

三、完整代码实现（带注释）

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

// 扩展欧几里得算法实现
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;
    }
    long long d = extended_gcd(b, a % b, y, x); // 递归调用
    y -= a / b * x; // 更新y值
    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的情况
    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;
    }
    
    // 处理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);
    if (c % d != 0) return 0;

    // 调整符号
    x0 *= (a < 0) ? -1 : 1;
    y0 *= (b < 0) ? -1 : 1;
    
    // 计算特解
    x0 *= -c / d;
    y0 *= -c / d;
    
    a /= d;
    b /= d;

    // 通解公式: x = x0 + b*t, y = y0 - a*t
    // 计算t的范围约束
    long long t_low = max(ceil((x1 - x0) * 1.0 / b), ceil((y0 - y2) * 1.0 / a));
    long long t_high = min(floor((x2 - x0) * 1.0 / b), floor((y0 - y1) * 1.0 / a));

    return (t_high >= t_low) ? (t_high - t_low + 1) : 0;
}

int main() {
    ios::sync_with_stdio(false); // 加速输入输出
    cin.tie(0); // 解除cin与cout的绑定
    
    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;
}

四、调试技巧

1. 测试边界条件(a=0或b=0)

2. 验证小规模数据

3. 检查符号处理是否正确

4. 观察中间变量的变化