AT_ACL1B Sum is Multiple 题解

记 $f(k) = 1 + 2 + \cdots + k = \dfrac12k(k+1)$。

首先，$f(n)$ 一定是 $n$ 的倍数，所以一定有解。

$n \mathop{|} f(k)$，则 $2n \mathop{|} k(k+1)$。

设 $d$ 为 $k$ 和 $2n$ 的公因数，并记 $k^\prime = \dfrac k d,\ n^\prime = \dfrac{2n}{d}$。

现要求这个 $d$ 满足 $k + 1$ 是 $n^\prime$ 的倍数。这样的 $d$ 必定存在，因为 $d = \gcd(k, 2n)$ 总满足条件。

此时，下面的方程组成立：

$$\displaylines{\begin{cases}
k \equiv 0 &\pmod d \\
k \equiv -1 &\pmod{n^\prime}
\end{cases}}$$

对于一个给定的 $d$，满足上面方程组的 $k$ 均满足 $n \mathop{|} f(k)$；对于一个给定的 $k$ 满足 $n \mathop{|} f(k)$，上面已指出必然存在一个 $d$ 使得上面方程组成立，即必然存在一个 $d$ 能找到这个 $k$。

所以，考虑枚举 $d$，解出对应方程组的最小正整数解，这些解中的最小即为所求的最小的 $k$。

$d$ 是 $2n$ 的因数，所以 $O(\sqrt n)$ 枚举即可。扩展欧几里得算法解出 $k$ 的最小正整数解的复杂度是 $O(\log n)$，而据 AT 官方题解，$2 \times 10^{15}$ 范围内的数因数个数不超过 $30720$，所以可以通过。

实现时要注意 long long 可能是不够的。我开了 __int128。