Description
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
思路：
1.如果x1>x2或者1>y2，不符合题意，无解.
2.只要a,b不同时为0，gcd(a,b)!=0,就可以带入扩欧函数,求得一组解，所以先判断a=0,b=0的情况，然后把a,b,带入函数，求得x,y,再讨论a,b分别为0的情况.
4.根据xx=x+k*d,yy=y-k*a(k属于Z)，带入x,y的上下界，求得整数k1,k2,k3,k4,使得k1<k2,k3<k4,然后求[k1,k2],[k3,k4]的交集.
注意：
ceil()为向上取整，floor()为向下取整.
代码：
</pre><pre name="code" class="cpp">#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
typedef long long ll;
ll mmax(ll a,ll b){return a>b?a:b;}
ll mmin(ll a,ll b){return a<b?a:b;}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b) {x=1;y=0;return a;}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main()
{
ll a,b,c,d,x1,x2,y1,y2,x,y,k1,k2,k3,k4;
cin>>a>>b>>c>>x1>>x2>>y1>>y2;c=-c;
if(x1>x2||y1>y2)
{
cout<<0<<endl;
return 0;
}
if(a==0&&b==0)
{
if(c==0)
cout<<(x2-x1+1)*(y2-y1+1)<<endl;
else
cout<<0<<endl;
return 0;
}
d=exgcd(a,b,x,y);
if(c%d)
{
cout<<0<<endl;
return 0;
}
a/=d,b/=d,c/=d;
x*=c,y*=c;
if(a==0)
{
if(y>=y1&&y<=y2)
cout<<x2-x1+1<<endl;
else
cout<<0<<endl;
return 0;
}
if(b==0)
{
if(x>=x1&&x<=x2)
cout<<y2-y1+1<<endl;
else
cout<<0<<endl;
return 0;
}
double aa=-a,bb=b,xx=x,yy=y,root_x1,root_x2,root_y1,root_y2;
root_x1=(x1-xx)/bb,root_x2=(x2-xx)/bb,root_y1=(y1-yy)/aa,root_y2=(y2-yy)/aa;
if(root_x1>root_x2) swap(root_x1,root_x2);
if(root_y1>root_y2) swap(root_y1,root_y2);
k1=ceil(root_x1),k2=floor(root_x2),k3=ceil(root_y1),k4=floor(root_y2);
cout<<mmin(k2,k4)-mmax(k1,k3)+1<<endl;
return 0;
}