106. The equation
time limit per test: 0.50 sec.
memory limit per test: 4096 KB
There is an equation ax + by + c = 0. Given a,b,c,x1,x2,y1,y2 you must determine, how many integer roots of this equation are satisfy to the following conditions : x1<=x<=x2, y1<=y<=y2. Integer root of this equation is a pair of integer numbers (x,y).
Input
Input contains integer numbers a,b,c,x1,x2,y1,y2 delimited by spaces and line breaks. All numbers are not greater than 108 by absolute value.
Output
Write answer to the output.
Sample Input
1 1 -3 0 4 0 4
Sample Output
4
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
__int64 exgcd(__int64 a,__int64 b,__int64 &x,__int64 &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
__int64 r=exgcd(b,a%b,x,y);
__int64 t=x;x=y;y=t-a/b*y;
return r;
}
int main()
{
__int64 a,b,c,x1,x2,y1,y2,x,y;
while(scanf("%I64d%I64d%I64d",&a,&b,&c)==3)
{
c=-c;
scanf("%I64d%I64d%I64d%I64d",&x1,&x2,&y1,&y2);
if(x1 > x2 || y1 > y2)
{
printf("0/n");
continue;
}
//特殊情况a和b有1个为0 和 a和b同时为0
if(!a||!b)
{
if(!a&&!b&&!c)//a和b同时为0
{
__int64 res1 = x2 - x1 + 1,res2 = y2 - y1 + 1;//会溢出,注意精度
res1 = res1 * res2;
printf("%I64d/n", res1);
continue;
}
else if(!a&&!b&&c) //a和b同时为0
{
printf("0/n");continue;
}
else if(!a&&b)//a和b有1个为0 a为0
{
if(c%b)
{
printf("0/n");continue;
}
else
{
y=c/b;
if(y>=y1&&y<=y2) printf("%I64d/n",x2-x1+1);
else printf("0/n");
continue;
}
}
else if(a&&!b)//a和b有1个为0 b为0
{
if(c%a)
{
printf("0/n");continue;
}
else
{
x=c/a;
if(x>=x1&&x<=x2) printf("%I64d/n",y2-y1+1);
else printf("0/n");
continue;
}
}
}
__int64 r=exgcd(a,b,x,y);
if(c%r)
{
printf("0/n");continue;
}
x*=c/r,y*=c/r;//算出一个解
__int64 _count=0;
__int64 lx, rx, ly, ry;
//x=x0+k*b/r,y=y0-k*a/r;
//* *r/b== * /(b/r),* *r/a== * /(b/a)
lx = (x1<=x || (x1-x)*r%b==0) ? (x1-x)*r/b : (x1-x)*r/b+1;
rx = (x2>=x || (x-x2)*r%b==0) ? (x2-x)*r/b : (x2-x)*r/b-1;
ly = (y1<=y || (y1-y)*r%a==0) ? (y-y1)*r/a : (y-y1)*r/a-1;
ry = (y2>=y || (y-y2)*r%a==0) ? (y-y2)*r/a : (y-y2)*r/a+1;
if (lx > rx) swap(lx, rx);
if (ly > ry) swap(ly, ry);
if (lx <= ry && ly <= rx) { //求出两个区间交集的元素个数
__int64 _max = (lx>ly) ? lx : ly;
__int64 _min = (rx<ry) ? rx : ry;
_count = _min-_max+1;
}
printf("%I64d/n",_count);
}
return 0;
}