CF2260B Monocarp and Projects

Monocarp 经营着一家公司。请考虑他公司接下来 $k$ 个月的运营情况。在第一个月，公司有 $x$ 名员工（不包括 Monocarp 自己），需要完成 $y$ 个项目。之后每个月，员工数和项目数都各自增加 $1$。 也就是说，在第 $i$ 个月（$0 \le i < k$），公司有 $x + i$ 名员工，需要完成 $y + i$ 个项目。 每个月，Monocarp 会将项目分配给员工。每个员工必须分配到相同数量的项目，并且每个项目最多只能分配给一名员工。所有未能分配给员工的项目由 Monocarp 自己完成。他总是选择一种分配方式，使得自己需要完成的项目数量最少。 具体来说，如果某个月有 $a$ 名员工和 $b$ 个项目，那么 Monocarp 会给每个员工分配恰好 $\left\lfloor \frac{b}{a} \right\rfloor$ 个项目，剩下的 $b \bmod a$ 个项目由他自己完成。 请计算接下来 $k$ 个月里，Monocarp 需要自己完成的项目总数。

第一行包含一个整数 $t$，表示测试用例数量（$1 \le t \le 10^4$）。 每个测试用例占一行，包含三个整数 $x$、$y$、$k$（$1 \le x \le y \le 10^6$；$1 \le k \le 10^{12}$）。 输入额外限制： - 所有测试用例的 $y$ 之和不超过 $10^6$。

对于每个测试用例，输出一个整数，表示 Monocarp 在接下来 $k$ 个月里需要自己完成的项目总数。

在第一个测试用例中，唯一的员工完成了唯一的项目，所以 Monocarp 不需要做项目。 在第二个测试用例中，第一个月由 $3$ 名员工完成 $10$ 个项目：每人得到 $3$ 个项目，Monocarp 完成 $1$ 个项目。第二个月由 $4$ 名员工完成 $11$ 个项目：每人得到 $2$ 个项目，Monocarp 完成 $3$ 个项目。答案为 $1 + 3 = 4$。 在第三个测试用例中，Monocarp 在六个月内分别需要完成 $2$、$1$、$0$、$5$、$5$、$5$ 个项目，它们的和为 $2 + 1 + 0 + 5 + 5 + 5 = 18$。 由 ChatGPT 5 翻译