Skip to content

洛谷 - P5596 题

题解约 1.3 千字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

小 X 遇到了一道题:

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

y2x2=ax+by^2 - x^2 = ax + b

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

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

#输入格式

一行两个整数 a,ba, b

#输出格式

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

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

#输入输出样例

样例输入 #1

5 15

样例输出 #1

1

样例解释 #1

(x,y)=(6,9)(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=0a = b = 0
  • Subtask 2(6 points):0a,b20 \le a,b \le 2,不存在无限个数的情况。
  • Subtask 3(9 points):0a,b1000 \le a,b \le 100,不存在无限个数的情况。
  • Subtask 4(13 points):0a,b1030 \le a,b \le 10^3,不存在无限个数的情况。
  • Subtask 5(14 points):0a1040 \le a \le 10^40b1070 \le b \le 10^7
  • Subtask 6(14 points):a=0a = 0
  • Subtask 7(14 points):b=0b = 0
  • Subtask 8(27 points):无特殊限制。

对于 100%100\% 的数据,0a1080 \le a \le 10^80b10150\le b \le 10^{15}

#思路

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

y2x2=ax+b(1)\tag{1} y^2 - x^2 = ax + b

(1)(1) 式进行移项,得:

y2b=x2+2ax(2)\tag{2} y^2 - b = x^2 + 2ax

(2)(2) 式右侧配方,得:

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

(3)(3) 式两侧同乘 44,得:

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

(4)(4) 式再次移项,得:

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

展开 (5)(5) 式左侧,得:

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

由题,显然 2x+a+2y>02x + a + 2y > 0,接下来分类讨论:

  1. a24b<0a^2 - 4b < 0 时,2x+a2y<02x + a - 2y < 0

    左右同乘 1-1,得:

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

    p=2y+2x+ap = 2y + 2x + aq=2y2xaq = 2y - 2x - a0<q<p0 < q < p),显然可以将 4ba24b - a^2 分解为两数之积可以得到一组 p,qp, q。又有:

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

    可以枚举 qq 再据此计算出 pp,进而再计算出 x,yx, y 的取值。

  2. a24b>0a^2 - 4b > 0 时,2x+a2y>02x + a - 2y > 0

    p=2x+a+2yp = 2x + a + 2yq=2x+a2yq = 2x + a - 2y0<q<p0 < q < p),显然可以将 a24ba^2 - 4b 分解为两数之积可以得到一组 p,qp, q。又有:

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

    可以枚举 qq 再据此计算出 pp,进而再计算出 x,yx, y 的取值。

  3. a24b=0a^2 - 4b = 0 时,2x+a2y=02x + a - 2y = 0

    a24b=0a^2 - 4b = 0 可知,aa 为偶数。可得 x+a2=yx + \frac{a}{2} = y

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

#代码

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;
}