正文
The equation - SGU 106（扩展欧几里得）
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
题目大意：有一个二元一次方程，给出系数值和x与y的取值范围，求出来总共有多少对整数解。
分析：有以下几点情况。
1，系数a=0， b=0， 当c ！= 0的时候结果很明显是无解，当c=0的时候x，y可以为任意值，答案就是（x2-x1+1）*（y2-y1+1）
2，系数a=0， b!=0, 先判断y的唯一解是否是整数，并且在[y1,y2]范围内，如果在，答案就是x的个数，x2-x1+1，否则为0
3，系数b=0, a!=0, 先判断x的唯一解是否是整数，并且在[x1,x2]范围内，如果在，答案就是y的个数，y2-y1+1，否则为0
4，上面的特殊情况考虑完毕，因为要求余，但是给的系数是有负数的，所以先把负数转换成正数，符号转变的时候其所对应的取值范围也应对应转变，求出来x0,y0后，再用给定的范围求出t的范围，取两者交叉范围就是答案，注意向上向下取整问题，而且x计算出来的t是递增的，y 计算出来的t是递减的，要做相应转变。
代码如下：
===========================================================================================================
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
typedef long long LL;
using namespace std;LL ExGcd(LL a, LL b, LL &x0, LL &y0)
{
if(b == )
{
x0 = , y0 = ;
return a;
} LL d = ExGcd(b, a%b, x0, y0); swap(x0, y0);
y0 = y0 - a/b*x0; return d;
}int main()
{
LL a, b, c, x1, x2, y1, y2, x0, y0, ans = ; cin >> a >> b >> c;
cin >> x1 >> x2 >> y1 >> y2; c = -c;
if(c < ){c=-c; a=-a, b=-b;}
if(a < ){a=-a; swap(x1, x2), x1=-x1, x2=-x2;}
if(b < ){b=-b; swap(y1, y2), y1=-y1, y2=-y2;} if(a == && b==)
{
if(c == )
cout<< (y2-y1+)*(x2-x1+) <<endl;
else
cout << "" <<endl;
return ;
} if(a == )
{
if(c % b == && c/b >= y1 && c/b <= y2)
cout << x2-x1+ <<endl;
else
cout << "" <<endl; return ;
}
if(b == )
{
if(c % a == && c/a >= x1 && c/a <= x2)
cout << y2-y1+ <<endl;
else
cout << "" <<endl;
return ;
} LL d = ExGcd(a, b, x0, y0); if(c % d == )
{
a /= d, b /= d, c/=d;
x0 *= c, y0 *= c; LL L = max( ceil(1.0*(x1-x0)/b), ceil(1.0*(y0-y2)/a) );
LL R = min( floor(1.0*(x2-x0)/b), floor(1.0*(y0-y1)/a) ); if(L <= R)
ans = R-L+;
} cout << ans <<endl; return ;
}
