# The Equation

## 题目描述

There is an equation $ax+by+c=0$. Given $a,b,c,x_1,x_2,y_1,y_2$ you must determine, how many integer roots of this equation are satisfy to the following conditions: $x_1 \le x \le x_2, \; y_1 \le y \le y_2$. Integer root of this equation is a pair of integer numbers $(x,y)$.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

namespace std {
template <typename T>
void maxify(T &a, T b) { b > a && (a = b); }
template <typename T>
void minify(T &a, T b) { b < a && (a = b); }
}

struct IOManager {
template <typename T>
inline bool read(T &x) {
char c; bool flag = false; x = 0;
while (~ c && ! isdigit(c = getchar()) && c != '-') ;
c == '-' && (flag = true, c = getchar());
if (! ~ c) return false;
while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
return (flag && (x = -x), true);
}
inline bool read(char &c) {
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
inline int read(char s[]) {
char c; int len = 0;
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
if (! ~ c) return 0;
while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
return (s[len] = '\0', len);
}
template <typename T>
inline IOManager operator > (T &x) {
read(x); return *this;
}
template <typename T>
inline void write(T x) {
x < 0 && (putchar('-'), x = -x);
x > 9 && (write(x / 10), true);
putchar(x % 10 + '0');
}
inline void write(char c) {
putchar(c);
}
inline void write(char s[]) {
int pos = 0;
while (s[pos] != '\0') putchar(s[pos ++]);
}
template <typename T>
inline IOManager operator < (T x) {
write(x); return *this;
}
} io;

struct Solver {
private:
int a, b, c, x1, x2, y1, y2, x, y, gcd;
void input() { io > a > b > c > x1 > x2 > y1 > y2; }
int ex_gcd(int a, int b, int &x, int &y) {
if (! b) { x = 1, y = 0; return a; }
int ret = ex_gcd(b, a % b, y, x); y -= a / b * x; return ret;
}
void process() {
if (! b) swap(a, b), swap(x1, y1), swap(x2, y2);
if (! b) {
if (c) io < 0 < '\n';
else io < (x2 - x1 + 1) * (y2 - y1 + 1) < '\n';
return;
}
gcd = ex_gcd(a, b, x, y);
if (c % gcd) { io < 0 < '\n'; return; }
a /= gcd, b /= gcd, c /= gcd, x *= -c, y *= -c;
if (b < 0) b = -b, a = -a;
x += 1000000000 * b, y -= 1000000000 * a;
y += ((x - x1) / b + 1) * a, x -= ((x - x1) / b + 1) * b;
x += b, y -= a;
if (x > x2) { io < 0 < '\n'; return; }
int ans = (x2 - x) / b + 1;
if (! a) {
if (y < y1 || y > y2) ans = 0;
} else {
int l = -1000000000, r = 1000000000, cnt = 0;
while (l + 1 < r) {
int mid = l + r >> 1;
if (y - a * mid < y1) if (a > 0) r = mid; else l = mid;
else if (a < 0) r = mid; else l = mid;
}
if (a < 0 && y - a * l == y1) -- l, -- r;
if (a > 0 && y - a * r == y1) ++ r, ++ l;
int l1 = l, r1 = r; l = -1000000000, r = 1000000000;
while (l + 1 < r) {
int mid = l + r >> 1;
if (y - a * mid < y2) if (a > 0) r = mid; else l = mid;
else if (a < 0) r = mid; else l = mid;
}
if (a < 0 && y - a * r == y2) ++ r, ++ l;
if (a > 0 && y - a * l == y2) -- l, -- r;
if (l > l1) swap(l, l1), swap(r, r1);
maxify(r, 0ll), minify(l1, ans - 1);
ans = l1 - r + 1;
}
io < ans < '\n';
}

public:
void solve() { input(), process(); }
} solver;

signed main() {
solver.solve();
return 0;
}


418 I'm a teapot