|
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
思路：
又是一道很明显的exgcd题，这次做完，感觉对exgcd了解更加多了。
对a要进行符号判断，负号就要变为正号，相对应的区间x1，x2也要取对称区间；b同理。c变换a，b也要一起变换（二元一次方程）。其他的可以参考之前写过的题：循环狂魔 和 青蛙也要找女朋友
一道解二元一次方程的题，最后一点并集那里画个图应该就能解决了。中间还有一些判断要分布讨论。
又找到一个ceil（）用来求向上取整（里面必须要double，和floor（）一样，不然提交就会CE...）
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<queue>
#include<cmath>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<vector>
#include<iostream>
#include<algorithm>
#include<sstream>
#define INF 0x3f3f3f3f
#define ll long long
const int N=10005;
const ll MOD=998244353;
using namespace std;
ll ex_gcd(ll a,ll b,ll &x,ll &y){
ll d,t;
if(b==0){
x=1;
y=0;
return a;
}
d=ex_gcd(b,a%b,x,y);
t=x-a/b*y;
x=y;
y=t;
return d;
}
int main(){
ll a,b,c,x1,x2,y1,y2,x,y;
cin>>a>>b>>c>>x1>>x2>>y1>>y2;
c=-c;
if(c<0){
c=-c;
a=-a;
b=-b;
}
if(a<0){
a=-a;
swap(x1,x2);
x1=-x1;
x2=-x2;
}
if(b<0){
b=-b;
swap(y1,y2);
y1=-y1;
y2=-y2;
}
ll d=ex_gcd(a,b,x,y);
if(a==0 || b==0){ //ax+by=-c
if(a==0 && b==0){
if(c==0){
cout<<(x2-x1+1)*(y2-y1+1)<<endl;
return 0;
}
else{
cout<<0<<endl;
return 0;
}
}
else if(a==0){
if(c%b==0 && c/b>=y1 && c/b<=y2){
cout<<(x2-x1+1)<<endl;
return 0;
}
else{
cout<<0<<endl;
return 0;
}
}
else if(b==0){
if(c%a==0 && c/a>=x1 && c/a<=x2){
cout<<(y2-y1+1)<<endl;
return 0;
}
else{
cout<<0<<endl;
return 0;
}
}
}
x=x*c/d;
y=y*c/d;
ll k1=b/d,k2=a/d;
if(c%d!=0){
cout<<0<<endl;
return 0;
}
else{
ll r=min(floor((x2-x)*1.0/k1),floor((y-y1)*1.0/k2)) ,l=max(ceil((x1-x)*1.0/k1),ceil((y-y2)*1.0/k2));
if(r>=l){
cout<<r-l+1<<endl;
}
else{
cout<<0<<endl;
}
}
return 0;
}