一开始以为是线性规划的题目，看了网上的提示说是求模线性方程。用拓展欧几里得算法可以得出原方程的一个解。然后就可以根据这个解判断在所给的区间里有几个解。题目比较纠结的地方是边界问题的判断，花了很多时间。以后要多做题才能更快地考虑好边界问题。
由ax+by+c = 0有ax+by = -c，两边取模b得到
ax+by ≡ -c (mod b) 推出 ax ≡ -c (mod b)
模线性方程有解当且仅当gcd(a,b) | -c，有解的情况下方程对模-c有d个不同的解，d=gcd(a,b)
根据拓展欧几里得算法可以算出x0, y0使得d = a*x0+b*y0
则x = x0*(-c/d), y = y0*(-c/d)为原方程ax+by+c=0的一个解
则方程的所有解为x = x0*(-c/d) + i*(b/d), y = y0*(-c/d) - i*(a/d)
计算所有的i使得解在所给区间内的个数即可。
#include <stdio.h>
typedef struct tagNode {
long long d; long long x; long long y;
} Node;
void swap(long long* a, long long* b) {
long long t = *a;
*a = *b;
*b = t;
}
Node euclid(long long a, long long b) {
Node t;
if (!b) {
t.d = a; t.x = 1; t.y = 0;
return t;
}
t = euclid(b, a % b);
Node t1;
t1.d = t.d; t1.x = t.y; t1.y = t.x-(a/b)*t.y;
return t1;
}
int main(void) {
long long a, b, c;
long long x1, x2, y1, y2;
scanf ("%I64d%I64d%I64d", &a, &b, &c);
c = -c;
scanf ("%I64d%I64d%I64d%I64d", &x1, &x2, &y1, &y2);
long long count = 0;
if (a==0 && b==0) {
if (c==0) {
count = (x2-x1+1)*(y2-y1+1);
}
} else if (a==0) {
if (c%b==0 && c/b>=y1 && c/b<=y2) {
count = x2-x1+1;
}
} else if (b==0) {
if (c%a==0 && c/a>=x1 && c/a<=x2) {
count = y2-y1+1;
}
} else { //如果a,b都不为0,用拓展欧几里得算出一个解
Node t = euclid(a, b);
if (c % t.d == 0) {
t.x *= c/t.d;
t.y *= c/t.d;
long long lx, rx, ly, ry;
lx = (x1<=t.x || (x1-t.x)*t.d%b==0) ? (x1-t.x)*t.d/b : (x1-t.x)*t.d/b+1;
rx = (x2>=t.x || (t.x-x2)*t.d%b==0) ? (x2-t.x)*t.d/b : (x2-t.x)*t.d/b-1;
ly = (y1<=t.y || (y1-t.y)*t.d%a==0) ? (t.y-y1)*t.d/a : (t.y-y1)*t.d/a-1;
ry = (y2>=t.y || (t.y-y2)*t.d%a==0) ? (t.y-y2)*t.d/a : (t.y-y2)*t.d/a+1;
if (lx > rx) {
swap(&lx, &rx);
}
if (ly > ry) {
swap(&ly, &ry);
}
if (lx <= ry && ly <= rx) { //求出两个区间交集的元素个数
long long max = (lx>ly) ? lx : ly;
long long min = (rx<ry) ? rx : ry;
count = min-max+1;
}
}
}
printf ("%I64d\n", count);
return 0;
}