SGU106 The equation

<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);"><span style="font-size:14px;">题意：给出直线ax+by+c=0的参数a, b, c，求直线在 x ∈[x1, x2]，y ∈[y1, y2] 上有多少整点。</span></span>
           

题解：首先特判a或b等于零的情况。若a,b非零，欧几里得搞出一组解，然后算出delta_x, delta_y（通解式子），按直线的斜率>0或<0分类。然后求出x的最小合法取值(即对应的y也合法)，然后在x的可滑动区间和y的可滑动区间之间求一个最小值就好了。

写这题的时候开始代码还能看，后来一次又一次地被细节坑，然后为了AC代码就越来越乱了。。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define LL long long
#define f1(y) ((c-b*(y)) / a) //已知y对应的x
#define f2(x) ((c-a*(x)) / b) //已知x对应的y
LL a, b, c;
LL x1, x2;
LL y1, y2;

LL Min(LL a, LL b) { return a<b ? a : b; }
LL Max(LL a, LL b) { return a>b ? a : b; }
LL Abs(LL x) { return x>0?x:-x; }

void exgcd(LL a, LL b, LL&d, LL&x, LL&y) {
	if (!b) { d = a; x = 1; y = 0; }
	else { exgcd(b, a%b, d, y, x); y -= x*(a/b); }
}

LL solve()
{
	LL g, x, y, minx, ry;
	exgcd(a, b, g, x, y);
	if (c % g != 0) return 0;
	x *= c / g;
	y *= c / g;
	LL dtx = b/g, dty = a/g;
	if (dtx < 0) dtx *= -1, dty *= -1;
	LL k1 = (x1 - x) / dtx, k2;
	x += k1 * dtx;
	x += (x1-x)/dtx*dtx;
	while (x < x1) x += dtx; //以上三行代码很冗余。为了AC，只有无节操乱搞了。
	if (dty<0) { //斜率>0
		dty *= -1;
		k2 = (y1 - y) / dty; //y的最小取值
		minx = Max(x, f1(y+k2*dty));//x的最小取值，要么是x最小，要么是y最小对应的x
		ry = f2(minx);
		if (ry > y2 || minx > x2) return 0;
		else return Min((x2-minx)/dtx+1, (y2-ry)/dty+1);
	}
	else { //斜率<0
		k2 = (y1 - y) / dty;
		y += k2 * dty;
		y += (y2 - y) / dty * dty;
		while (y+dty<=y2) y += dty;//搞出y的最大取值
		minx = Max(x, f1(y)); //x的最小取值，要么是x最小，要么是y最大对应的x
		ry = f2(minx);
		if (ry < y1 || minx > x2) return 0;
		else return Min((x2-minx)/dtx+1, (ry-y1)/dty+1);
	}
}

LL special()
{
	if (a==0 && b==0)
		return (c==0) * (x2-x1+1) * (y2-y1+1);
	if (a==0) {
		if (c % b != 0 || c/b<y1 || c/b>y2) return 0;
		return x2 - x1 + 1;
	}
	else {
		if (c % a != 0 || c/a<x1 || c/a>y2) return 0;
		return y2 - y1 + 1;
	}
}

int main()
{
	cin >> a >> b >> c;
	c = -c;
	cin >> x1 >> x2;
	cin >> y1 >> y2;
	if (x1>x2 || y1>y2) cout<<"0\n";
	else if (a==0 || b==0) cout << special() << '\n';
	else cout << solve() << '\n';
	return 0;
}