题目描述
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)$.
题意概述
求二元一次方程$ax+by+c=0$满足$x_1 \le x \le x_2 \land y_1 \le y \le y_2$的整数解的个数。
数据范围:$-10^8 \le a, b, c, x_1, x_2, y_1, y_2 \le 10^8$。
算法分析
先判断是否有解。若$a=b=0 \land c \neq 0 \lor (a, b) \nmid c$则无解。
之后我们计算出$g=(a, b)$,令$a’={a \over g}, \; b’={b \over g}, \; c’={c \over g}$,方程变为$a’x+b’y=-c’$,用扩展GCD求出它的一组解$(x, y)$,那么该方程的通解为$(x+kb’, y-ka’)$。
分别计算使$x, y$满足要求的$k$的范围,其交集的大小就是答案。在计算范围时可以二分查找。
代码
#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; }