题目链接：
SGU 106 The equation
题意：
给出a,b,c,x1,x2,y1,y2求满足ax + by + c = 0且x1 <= x <= x2, y1 <= y <= y2的x,y有多少组。
分析：
扩展欧几里德的应用需要特别注意a=0,b=0,c=0的特判。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
double eps = 1e-8;ll a, b, c, x1, yy1, x2, y2, ans;ll ex_gcd(ll n, ll m, ll& x, ll& y) //返回值是gcd(a, b)
{if(m == 0){x = 1, y = 0;return n;}ll d = ex_gcd(m, n % m, y, x);y -= n / m * x;return d;
}void ModularLinearEquation() //模线性方程组
{ll x, y, x0, y0;ll d = ex_gcd(a, b, x, y);//求解方程ax + by = gcd(a, b)if(c % d) {printf("0\n");return ;}//此时的x, y是方程ax + by = gcd(a, b)的一组基础解a /= d, b /= d, c /= d;x0 = x * c, y0 = y * c; //x0, y0是ax + by = c 的一组基础解//a * x + b * y = c通解满足：a * (x0 + k * b) + b * (y0 - k * a) = c//所以：x = x0 + k * b ...①, y = y0 - k * a ...②, k ∈ Z//先求出满足①：x1 <= x0 + k * b <= x2的k的范围[l1, r1]//再求出满足②:yy1 <= y0 - k * a <= y2的k的范围[l2, r2]两者取交集即可//l1 = ceil((x1 - x0)/b)，r1 = floor((x2 - x0)/b)//l2 = ceil((y0 - y2)/a), r2 = floor((y0 - yy1)/a) ll l1 = (ll)ceil((double)(x1 - x0) / b);ll r1 = (ll)floor((double)(x2 - x0) / b);ll l2 = (ll)ceil((double)(y0 - y2) / a);ll r2 = (ll)floor((double)(y0 - yy1) / a);ll l = max(l1, l2), r = min(r1, r2);ans = (r - l + 1 < 0) ? 0 : (r - l + 1);printf("%lld\n", ans);return ;
}int main()
{while(~scanf("%lld%lld%lld", &a, &b, &c)){scanf("%lld%lld%lld%lld", &x1, &x2, &yy1, &y2);int flag = 0;c = -c; //移项，得到方程a * x + b * y = -c//下面将方程的所有系数a, b, c变为非负数if(c < 0){c = -c , a = -a, b = -b;}if(a < 0){ //需要将a取相反数，相当于把x也取了相反数，所以需要将[x1, x2]的范围变为[-x2, -x1]ll tmpx1 = x1, tmpx2 = x2;x1 = -tmpx2, x2 = - tmpx1;a = -a;}if(b < 0){ //同理ll tmpyy1 = yy1, tmpy2 = y2;yy1 = -tmpy2, y2 = -tmpyy1;b = -b;}if(a == 0 && b == 0) { //0 * x + 0 * y = cflag = 1; if(c == 0) ans = (x2 - x1 + 1) * (y2 - yy1 + 1);else ans = 0;}else if(a == 0){ // b != 0flag = 1;if(c % b == 0){ // 0 * x + b * y = c --> b * y = cll tmpy = c / b;if(yy1 <= tmpy && tmpy <= y2) ans = x2 - x1 + 1;else ans = 0;}else ans = 0;}else if(b == 0) { //a != 0flag = 1;if(c % a == 0) { // a * x + 0 * y = c --> a * x = cll tmpx = c / a;if(x1 <= tmpx && tmpx <= x2) ans = y2 - yy1 + 1;else ans = 0;}else ans = 0;}//以上处理完了a = 0或者b = 0的所有特例if(flag) {printf("%lld\n", ans);continue;}ModularLinearEquation();}return 0;
}