「TFOI R1」Average Number 题解
Shadovv
·
·
题解
出题人题解。
原本预估的难度是黄，但是从反馈来看的话难度是绿（
题意应该很清楚，我的解法是推式子+缩放，一些奇怪的方法可以看 Super_Cube 的题解。
\begin{aligned}
&\dfrac{\dfrac{n \times (n + 1)}{2} - m}{n - 1}\\
=&\dfrac{n \times (n + 1) - 2 \times m}{2 \times (n - 1)}\\
=&\dfrac{n \times (n - 1) + 2 \times n - 2 \times m}{2 \times (n - 1)}\\
=&\dfrac{n}{2} + \dfrac{n - m}{n - 1}\\
=&a + \dfrac{b}{c}\\
\end{aligned}
接下来是缩放，也是我认为的这一道题最精彩的部分。
注意到 1 \leqslant m \leqslant n，所以 0 \leqslant n - m \leqslant n - 1。
所以 0 \leqslant \dfrac{n - m}{n - 1} \leqslant 1。
带入到上面的式子后就是：
\dfrac{n}{2} \leqslant \dfrac{n}{2} + \dfrac{n - m}{n - 1} = a + \dfrac{b}{c} \leqslant \dfrac{n}{2} + 1
因为 \dfrac{b}{c} 是最简真分数（也就是小于 1），所以又有：
\dfrac{n}{2} - 1 < a \leqslant \dfrac{n}{2} + 1
把它拆成两个不等式并化简：
\begin{cases}
n < 2\times a + 2\\
2 \times a - 2 \leqslant n
\end{cases}
（因为 n 是正整数，所以 n < 2\times a + 2 等价于 n \leqslant 2\times a + 1）
最后就得到了：2 \times a - 2 \leqslant n \leqslant 2 \times a + 1。
于是可以在这个范围枚举 n，也就带一个四倍的常数。
$$
\begin{aligned}
\dfrac{\dfrac{n \times (n + 1)}{2} - m}{n - 1}&= \dfrac{a \times c + b}{c}\\
\dfrac{n \times (n + 1)}{2} - m&= \dfrac{(n - 1) \times (a \times c + b)}{c}\\
m&= \dfrac{n \times (n + 1)}{2} - \dfrac{(n - 1) \times (a \times c + b)}{c}\\
\end{aligned}
$$
因为 $m$ 也是正整数，所以要检查一下 $c$ 能不能整除 $n - 1$。
要注意上面的式子算出来的 $m$ 仍然可能不合法（比如出现负数），以及 $a = 1$ 时 $2 \times a - 2 = 0$ 但是 $n \geqslant 2$ 要判断一下。
运算过程中变量可能超 `long long`，记得开 `__int128` 还有优化运算顺序。
最后给出代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define getchar gc
typedef __int128 ll;
#define fu(i, l, r) for(ll i = l; i <= r; ++i)
char gc() {static char ibuf[1 << 20], *p1 = ibuf, *p2 = ibuf; return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1000010, stdin), p1 == p2) ? -1 : *p1++;}
void read(ll& x) {x = 0; int f = 1; char ch = getchar(); while(ch < '0' || ch > '9') f *= ((ch == '-') ? -1 : 1), ch = getchar(); while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); x *= f;}
ll t, m, a, b, c;
int main() {
read(t);
while(t--) {
read(a), read(b), read(c);
fu(i, max(2 * a - 2, (ll)2), 2 * a + 1) {
if((i - 1) % c) continue;
m = i * (i + 1) / 2 - (i - 1) / c * (a * c + b);
if(m < 1 || m > i) continue;
printf("%lld %lld\n", (long long)i, (long long)m);
break;
}
}
return 0;
}
```