H - The equation——（SGU 106）

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## H - The equation——（SGU 106）

angel_imp 2016-03-19 19:20:00 浏览805

``````
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

Sample Input

1 1 -3
0 4
0 4

Sample Output

4

``````

``````#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;

#define MM(a) memset(a,0,sizeof(a))

typedef long long LL;
typedef unsigned long long ULL;
const int MAXN = 1e7+5;
const int mod = 1000000007;
const double eps = 1e-7;

void Ex_gcd(LL a, LL b, LL &x, LL &y)
{
if(b == 0)
{
x = 1;
y = 0;
return;
}
LL x1, y1;
Ex_gcd(b, a%b, x1, y1);
x = y1;
y = x1 - (a/b)*y1;
}
LL GCD(LL a, LL b)
{
if(b == 0)
return a;
return GCD(b, a%b);
}
int main()
{
LL a, b, c, x, y, x1, x2, y1, y2, lx, ly, rx, ry, dx, dy, p;
while(cin>>a>>b>>c)
{
cin>>x1>>y1>>x2>>y2;
c = -c;
if(x1>y1 ||x2>y2)
puts("0");
else if(a==0 && b==0 && c==0)
cout<<(y1-x1+1)*(y2-x2+1)<<endl;
else if(a==0 && b==0)
puts("0");
else if(a == 0)
{
if(c%b || c/b>y2 || c/b<y1)
puts("0");
else
printf("%lld\n",y1-x1+1);
}
else if(b == 0)
{
if(c%a || c/a>x2 || c/a<x1)
puts("0");
else
printf("%lld\n",y2-x2+1);
}
else
{
LL d = GCD(abs(a), abs(b));
if(c % d)
puts("0");
else
{
a /= d;
b /= d;
c /= d;
Ex_gcd(abs(a), abs(b), x, y);
x *= c, y *= c;
///cout<<x<<" "<<y<<" "<<endl;
if(a < 0)
x = -x;
if(b < 0)
y = -y;
dx = abs(b), dy = abs(a);
p = (x%dx-x1%dx+2*dx) % dx;
lx = x1 + p;
///cout<<lx<<endl;0
p = (x%dx-y1%dx+2*dx) % dx;
rx = y1 + p - (p == 0 ? 0 : dx);
///cout<<rx<<endl;
if(lx > rx)
puts("0");
else
{
ly = (c-a*lx) / b, ry = (c-a*rx) / b;
if(ly > ry)
swap(ly, ry);
if(ly > y2 || ry < x2)
puts("0");
else
{
if(ly < x2)
{
p = (y%dy-x2%dy+2*dy) % dy;
ly = x2 + p;
}
if(ry > y2)
{
p = (y%dy-y2%dy+2*dy) % dy;
ry = y2 + p - (p == 0 ? 0 : dy);
}
printf("%lld\n", (ry - ly) / dy + 1);
}
}
}
}
}
return 0;
}
``````

angel_imp
+ 关注

corcosa 10283人浏览