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)$.

题意概述

求二元一次方程$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;
}