传送门

Sol

易得：ac+bc=(∑i=1ni)−mn−1\frac{ac + b}{c} = \frac{\left(\sum_{i = 1}^{n} i\right) - m}{n - 1}。

因为 $\left(\sum_{i = 1}^{n} i\right) - m \in \mathbb{Z} $，则 n−1=s×cn - 1 = s \times c，(∑i=1ni)−m=s×(ac+b)\left(\sum_{i = 1}^{n} i\right) - m = s \times (ac + b)。

不难发现，ss 是我们需要找的一个整数值，当 m∈[1,n]m \in [1, n] 时，此时有解且我们能够找到答案。

因此我们只需二分 ss 的值即可。

随着 ss 的增加，∑i=1ni\sum_{i = 1}^{n} i 比 s×(ac+b)s \times (ac + b) 增长的快，mm 逐渐变大，因此，二分查找时算出的 mm 如果大于 nn 时，ss 过于大，进行缩小，如果小于 11，则扩大。

对于 m∈[1,n]m \in [1, n] 的情况，应当缩小（或不变）。

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
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        __int128 a, b, c;
        long long a1, a2, a3;
        cin >> a1 >> a2 >> a3;
        a = a1, b = a2, c = a3;
        b += a * c;
        __int128 l, r;
        l = 1, r = 1e18, r /= c;
        while (l < r) {
            __int128 mi;
            mi = (l + r) / 2;
            __int128 x, y;
            x = mi * c, y = mi * b;
            __int128 vv;
            x++, vv = x, x = x * x + x, x /= 2, x -= y;
            if (x < 1)
                l = mi + 1;
            else
                r = mi;
        }
        __int128 x, y, z;
        x = r * c, y = r * b, x++, z = x, x = x + x * x, x /= 2, x -= y, a1 = z, a2 = x;
        cout << a1 << " " << a2 << '\n';
    }
}