和与积 题解 简单二分查找

题目大意：

给定两个整数 \(a(2 \le a \le 2 \times 10^9)\) 和 \(b(1 \le b \le 10^{18})\)。

判断是否存在两个正整数 \(x\) 和 \(y\)，同时满足如下两个条件：

1. \(x + y = a\)
2. \(x \times y = b\)

解题思路：

用 \(a - x\) 表示 \(y\)，可以得到面积的表达式为 \(x \times (a - x)\)，然后可以发现在区间 \([1, \frac{a}{2}]\) 范围内，\(x \times (a-x)\) 随着 \(x\) 的增大而增加，具有单调性，可以二分。

比如，\(a = 50\) 时，在区间 \([1, 25]\) 范围内 \(x\) 和 \(x \times (a - x)\) 的对应关系如下图所示：

然后就发现可以二分查找答案。

示例程序：

#include <bits/stdc++.h>
using namespace std;

int T;
long long a, b;

bool check() {
    long long l = 1, r = a / 2;
    while (l <= r) {
        long long mid = (l + r) / 2;
        if (mid * (a - mid) == b)
            return true;
        else if (mid * (a - mid) < b)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return false;
}

int main() {
    cin >> T;
    while (T--) {
        cin >> a >> b;
        puts(check() ? "YES" : "NO");
    }
    return 0;
}