等式 - 题目列表

题意

给定：

$a x + b y + c = 0$

以及矩形范围：

$x \in [x_1, x_2]$
$y \in [y_1, y_2]$

要求满足条件的整数解 (x, y) 有多少对。

思路

先看一个最直接的小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 a, b, c, x1, x2, y1, y2;
    cin >> a >> b >> c >> x1 >> x2 >> y1 >> y2;

    if (x1 > x2) {
        swap(x1, x2);
    }
    if (y1 > y2) {
        swap(y1, y2);
    }

    long long answer = 0;
    for (i64 x = x1; x <= x2; x++) {
        for (i64 y = y1; y <= y2; y++) {
            if (a * x + b * y + c == 0) {
                answer++;
            }
        }
    }

    cout << answer << '\n';
    return 0;
}

暴力版就是直接枚举矩形里的所有整数点，看它们是否满足方程。
这个思路很好理解，但区间很大时显然不能枚举。

先把方程改写成：

$a x + b y = -c$

若 a,b 都不为 0，设：

$d = \gcd(a,b)$

那么方程有整数解的充要条件是：

d 能整除 $-c$

若无解，答案就是 0。

若有解，用 exgcd 求出一组特解 (x0, y0)。
所有整数解可以写成：

$x = x_0 + k \cdot (b/d)$
$y = y_0 - k \cdot (a/d)$

这里 k 是任意整数。

接下来关键就变成：

哪些 k 会让 x 落在 [x1, x2]
哪些 k 会让 y 落在 [y1, y2]

只要分别把这两个条件转成对 k 的区间限制，再求交集大小即可。

这张图表示的就是这个过程：

flowchart LR
  A["通解：x=x0+k·b/d"] --> C["由 x 范围推出 k 区间"]
  B["通解：y=y0-k·a/d"] --> D["由 y 范围推出 k 区间"]
  C --> E["区间求交"]
  D --> E

图里真正要看的，是“二维平面里的点计数”已经被压成了“一维参数 k 的区间计数”。

另外还要单独处理几种退化情况：

$a = 0, b = 0$
$a = 0$
$b = 0$

因为这时通解形式会更简单，直接特判更稳。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using i128 = __int128_t;

const i64 INF64 = (1LL << 60);

i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    i64 d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

i64 floor_div(i128 a, i128 b) {
    if (b < 0) {
        a = -a;
        b = -b;
    }
    if (a >= 0) {
        return (i64) (a / b);
    }
    return (i64) (-((-a + b - 1) / b));
}

i64 ceil_div(i128 a, i128 b) {
    if (b < 0) {
        a = -a;
        b = -b;
    }
    if (a >= 0) {
        return (i64) ((a + b - 1) / b);
    }
    return (i64) (-((-a) / b));
}

bool add_constraint(i64 x0, i64 step, i64 L, i64 R, i64 &kl, i64 &kr) {
    if (L > R) {
        return false;
    }

    if (step == 0) {
        return L <= x0 && x0 <= R;
    }

    i64 l, r;
    if (step > 0) {
        l = ceil_div((i128) L - x0, step);
        r = floor_div((i128) R - x0, step);
    }
    else {
        l = ceil_div((i128) R - x0, step);
        r = floor_div((i128) L - x0, step);
    }

    kl = max(kl, l);
    kr = min(kr, r);
    return kl <= kr;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 a, b, c, x1, x2, y1, y2;
    cin >> a >> b >> c >> x1 >> x2 >> y1 >> y2;

    if (x1 > x2) {
        swap(x1, x2);
    }
    if (y1 > y2) {
        swap(y1, y2);
    }

    i64 rhs = -c;

    if (a == 0 && b == 0) {
        if (rhs == 0) {
            cout << (i64) ((i128) (x2 - x1 + 1) * (y2 - y1 + 1)) << '\n';
        }
        else {
            cout << 0 << '\n';
        }
        return 0;
    }

    if (a == 0) {
        if (rhs % b != 0) {
            cout << 0 << '\n';
            return 0;
        }
        i64 y = rhs / b;
        if (y1 <= y && y <= y2) {
            cout << (x2 - x1 + 1) << '\n';
        }
        else {
            cout << 0 << '\n';
        }
        return 0;
    }

    if (b == 0) {
        if (rhs % a != 0) {
            cout << 0 << '\n';
            return 0;
        }
        i64 x = rhs / a;
        if (x1 <= x && x <= x2) {
            cout << (y2 - y1 + 1) << '\n';
        }
        else {
            cout << 0 << '\n';
        }
        return 0;
    }

    i64 x0, y0;
    i64 d = exgcd(llabs(a), llabs(b), x0, y0);

    if (a < 0) {
        x0 = -x0;
    }
    if (b < 0) {
        y0 = -y0;
    }

    if (rhs % d != 0) {
        cout << 0 << '\n';
        return 0;
    }

    i64 mul = rhs / d;
    i64 base_x = (i128) x0 * mul;
    i64 base_y = (i128) y0 * mul;
    i64 step_x = b / d;
    i64 step_y = -a / d;

    i64 kl = -INF64, kr = INF64;
    if (!add_constraint(base_x, step_x, x1, x2, kl, kr)) {
        cout << 0 << '\n';
        return 0;
    }
    if (!add_constraint(base_y, step_y, y1, y2, kl, kr)) {
        cout << 0 << '\n';
        return 0;
    }

    cout << (kr - kl + 1) << '\n';
    return 0;
}

复杂度

主过程是一遍 exgcd 加上常数次区间计算：

$O(\log \max(|a|, |b|))$

空间复杂度：

$O(1)$

总结

这题的关键不是“矩形里数点”，而是先把方程的整数解写成通解。

一旦写出：

$x = x_0 + k \cdot (b/d)$
$y = y_0 - k \cdot (a/d)$

后面的问题就只剩下：

参数 k 有多少个合法取值

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

等式

目录

题意

思路

代码

复杂度

总结

一图流解析