洛谷 - P5596 题

#题面

#题目描述

小 X 遇到了一道题：

给定自然数 $a, b$，求满足下列条件的自然数对 $(x, y)$ 的个数：

$$y^2 - x^2 = ax + b$$

他不会，只好求助于精通数学的你。

如果有无限多个自然数对满足条件，那么你只需要输出 inf 即可。

#输入格式

一行两个整数 $a, b$。

#输出格式

如果个数有限，一行一个整数，表示个数。

如果个数无限，一行一个字符串 inf。

#输入输出样例

样例输入 #1

5 15

样例输出 #1

1

样例解释 #1

$(x, y) = (6, 9)$.

样例输入 #2

4 4

样例输出 #2

inf

样例输入 #3

12 6

样例输出 #3

0

样例输入 #4

96 96

样例输出 #4

7

样例输入 #5

10000 9999997

样例输出 #5

6

#数据范围与约定

本题采用捆绑测试。

• Subtask 1（3 points）：$a = b = 0$。
• Subtask 2（6 points）：$0 \le a,b \le 2$，不存在无限个数的情况。
• Subtask 3（9 points）：$0 \le a,b \le 100$，不存在无限个数的情况。
• Subtask 4（13 points）：$0 \le a,b \le 10^3$，不存在无限个数的情况。
• Subtask 5（14 points）：$0 \le a \le 10^4$，$0 \le b \le 10^7$。
• Subtask 6（14 points）：$a = 0$。
• Subtask 7（14 points）：$b = 0$。
• Subtask 8（27 points）：无特殊限制。

对于 $100\%$ 的数据，$0 \le a \le 10^8$，$0\le b \le 10^{15}$。

#思路

先观察题目中给出的这个式子：

$$\tag{1} y^2 - x^2 = ax + b$$

对 $(1)$ 式进行移项，得：

$$\tag{2} y^2 - b = x^2 + 2ax$$

对 $(2)$ 式右侧配方，得：

$$\tag{3} y^2 - b = (x + \frac{a}{2})^2 - \frac{a^2}{4}$$

将 $(3)$ 式两侧同乘 $4$，得：

$$\tag{4} 4y^2 - 4b = (2x + a)^2 - a^2$$

对 $(4)$ 式再次移项，得：

$$\tag{5} a^2 - 4b = (2x + a)^2 - 4y^2$$

展开 $(5)$ 式左侧，得：

$$\tag{6} a^2 - 4b = (2x + a + 2y) (2x + a - 2y)$$

由题，显然 $2x + a + 2y > 0$，接下来分类讨论：

1. 当 $a^2 - 4b < 0$ 时，$2x + a - 2y < 0$：

   左右同乘 $-1$，得：

   $$\tag{7} 4b - a^2 = (2y + 2x + a) (2y - 2x - a)$$

   记 $p = 2y + 2x + a$，$q = 2y - 2x - a$（$0 < q < p$），显然可以将 $4b - a^2$ 分解为两数之积可以得到一组 $p, q$。又有：

   $$\begin{aligned} p + q &= 4y \\ p - q &= 4x + 2a \Rarr p - q - 2a = 4x \\ \end{aligned}$$

   可以枚举 $q$ 再据此计算出 $p$，进而再计算出 $x, y$ 的取值。

2. 当 $a^2 - 4b > 0$ 时，$2x + a - 2y > 0$：

   记 $p = 2x + a + 2y$，$q = 2x + a - 2y$（$0 < q < p$），显然可以将 $a^2 - 4b$ 分解为两数之积可以得到一组 $p, q$。又有：

   $$\begin{aligned} p + q &= 4x + 2a \Rarr p + q - 2a = 4x \\ p - q &= 4y \\ \end{aligned}$$

   可以枚举 $q$ 再据此计算出 $p$，进而再计算出 $x, y$ 的取值。

3. 当 $a^2 - 4b = 0$ 时，$2x + a - 2y = 0$：

   由 $a^2 - 4b = 0$ 可知，$a$ 为偶数。可得 $x + \frac{a}{2} = y$。

   显然对于任意一个 $x$ 都有一个与其对应的 $y$ 满足条件。此时有无穷多组解。

#代码

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

#include <cmath>
#include <iostream>

using std::cin;
using std::cout;
const char endl = '\n';

long long a, b, d, m, ans;

int main() {
    std::ios::sync_with_stdio(false);

    cin >> a >> b;

    d = a * a - b * 4;

    if (d == 0) {
        cout << "inf" << endl;

        exit(0);
    } else if (d < 0) {
        d *= -1;
        m = std::sqrt(d);

        for (long long q = 1; q <= m; q++) {
            if (d % q == 0) {
                long long p = d / q;

                long long x = p - q - 2 * a,
                          y = p + q;

                if (x % 4 || y % 4) continue;

                x /= 4, y /= 4;

                if (x >= 0 && y >= x) ans++;
            }
        }
    } else {  // d > 0
        m = std::sqrt(d);

        for (long long q = 1; q <= m; q++) {
            if (d % q == 0) {
                long long p = d / q;

                long long x = p + q - 2 * a,
                          y = p - q;

                if (x % 4 || y % 4) continue;

                x /= 4, y /= 4;

                if (x >= 0 && y >= x) ans++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}