|
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
大意：给你a,b,c,x1,y1,x2,y2。让你求ax+by+c=0在区间[x1,x2],[y1,y2]的整数解个数。
考虑扩展欧几里得： 得到特解x0,y0后。设a=a/gcd,b=b/gcd。通解为x=x0+b*k,y=y0-a*k;
则 得到不等式 x1<=x+b*k<=x2,y1<=y-a*k<=y2。
解k的范围，取交集就好了。注意考虑向上取整与向下取整。
比如下界就应该是想上取整，上界应该向下取整。
#include <iostream>
#include <algorithm>
#define maxn 2025
using namespace std;
typedef long long ll;
ll ans=0;
ll L=-1e9,R=1e9;
ll ex_gcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
ll ans=ex_gcd(b,a%b,x,y);
ll temp=x;
x=y;
y=temp-(a/b)*x;
return ans;
}
ll down(ll x,ll y)//向下取整
{ ll res=0;
res=x/y;
if(x<0||y<0)
{
if(x%y!=0)
{
res--;
}
}
return res;
}
ll upper(ll x,ll y)//向上取整
{ ll res=x/y;
if(x>0&&y>0||x<0&&y<0)
{
if(x%y!=0)
{
res++;
}
}
return res;
}
void sovle(ll l,ll r,ll b)
{
if(b<0)
{
l=-l;
r=-r;
b=-b;
swap(l,r);
}
L=max(L,upper(l,b));
R=min(R,down(r,b));
}
int main()
{
int n;
ll a,b,c,x1,y1,x2,y2;
cin>>a>>b>>c>>x1>>x2>>y1>>y2;
c=-c;
if(a==0&&b==0&&c!=0)
{
ans=0;
}
else if(a==0&&b==0&&c==0)
{
ans=(x2-x1+1)*(y2-y1+1);
}
else if(a==0&&b!=0)
{
if(c%b==0)
{
ll y=c/b;
if(y>=y1&&y<=y2)
{
ans++;
}
}
}
else if(b==0&&a!=0)
{
if(c%a==0)
{
ll x=c/a;
if(x>=x1&&x<=x2)
{
ans++;
}
}
}
else
{ ll x,y;
ll gcd=ex_gcd(a,b,x,y);
if(c%gcd==0)
{ x=x*c/gcd;
y=y*c/gcd;
a/=gcd;
b/=gcd;
ll lx=x1-x,rx=x2-x;
ll ly=y1-y,ry=y2-y;
sovle(lx,rx,b);
sovle(ly,ry,-a);
ans=R-L+1;
}
}
cout<<ans<<endl;
return 0;
}