定义函数 \(f_a(x) = \lfloor \frac{x}{a} \rfloor + x \mod a\) 。
回答 \(q\) 个独立询问，每个询问给出 \(l, r, a(1 \leq l,r,a \leq 10^9)\) ，询问 \(f_a(x)\) 在定义域 \([l,r]\) 上的最大值为多少？
不妨先讨论出 \([0, +\infty]\) 上的 \(f_a(x)\) 图像
\[\begin{cases}
0 + x \mod a, \quad x \in [0, a - 1], \\
1 + x \mod a, \quad x \in [a, 2a - 1], \\
2 + x \mod a, \quad x \in [2a, 3a - 1], \\
\cdots;
\end{cases}
\]
不难发现 \(f_a(x)\) 在 \([0, +\infty]\) 上是分段递增的，断点在 \(x \equiv 0 (\mod a)\) 且在更小值处实心。
于是给定任意 \(l, r\) 。
- 若 \(l > \lfloor \frac{r}{a} \rfloor a - 1\) ，则最大值在 \(r\) 上。
- 否则最大值可能在 \(r\) 或 \(\lfloor \frac{r}{a} \rfloor a - 1\) 上。
于是让 \(l = max(l, \lfloor \frac{r}{a} \rfloor a - 1)\) ，则最大值在 \(l\) 或 \(r\) 上。
view
#include <bits/stdc++.h>
void solve() {
int l, r, a; std::cin >> l >> r >> a;
l = std::max(l, (r / a) * a - 1);
auto fun = [&](long long x) { return 1LL * (x / a) + x % a; };
std::cout << std::max(fun(r), fun(l)) << '\n';
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}