H - The equation
Time Limit:250MS Memory Limit:4096KB 64bit IO Format:%I64d & %I64u
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
我的思路就是首先把一个基本解求出来，然后看在x1、x2的范围内x的范围是多少，然后找到对应的y的范围，再看y的范围有多少个解是在y1、y2范围之内的，这个就是最后的答案。
当然，对于含有a=0或b=0的情况要特判一下。
附上一个很不错的网址：传送门
#include <iostream>
using namespace std;
typedef long long LL;
LL a,b,c,x1,x2,y1,y2,x,y,tmp,ans=;
LL mini = -361168601842738790LL;
LL maxi = 322337203685477580LL;
int extendedGcd(int a,int b){
if (b==){
x=;y=;
return a;
}
else{
int tmp = extendedGcd(b,a%b);
int t = x;
x=y;
y=t-a/b*y;
return tmp;
}
}
LL extendedGcd(LL a,LL b){
if (b == ){
x=;y=;
return a;
}
else{
LL TEMP = extendedGcd(b,a%b);
LL tt=x;
x=y;
y=tt-a/b*y;
return TEMP;
}
}
LL upper(LL a,LL b){
if (a<=)
return a/b;
return (a-)/b + ;
}
LL lower(LL a,LL b){
if (a>=)
return a/b;
return (a+)/b - ;
}
void update(LL L,LL R,LL wa){
if (wa<){
L=-L;R=-R;wa=-wa;
swap(L,R);
}
mini=max(mini,upper(L,wa));
maxi=min(maxi,lower(R,wa));
}
int main(){
cin >> a >> b >> c >> x1 >> x2 >> y1 >> y2;c=-c;
if (a== && b==){
if (c==) ans = (x2-x1+) * (y2-y1+);
}
else if (a== && b!=){
if (c % b==) {
tmp = c/b;
if (tmp>=y1 && tmp<=y2) ans = ;
}
}
else if (a!= && b==){
if (c % a==){
tmp = c/a;
if (tmp>=x1 && tmp<=x2) ans = ;
}
}
else{
LL d = extendedGcd(a,b);
if (c%d == ){
LL p = c/d;
update(x1-p*x,x2-p*x,b/d);
update(y1-p*y,y2-p*y,-a/d);
ans = maxi-mini+;
if (ans<) ans=;
}
}
cout << ans << endl;
}