题解：P15057 [UOI 2023 II Stage] Roads of Potokolandiya

zzxw · 2026-01-26 21:31:02 · 题解

结论：图连通的充要条件是 n=2^k，否则 1 和 n 不连通。

必要性：从 1 出发到达的点必定形如 2^a-bn。要求 2^a-bn=2^k，则 n=\dfrac{2^a}b，必定只含质因子 2。

充分性：当 n=2^k，从二进制角度想，x \leftarrow 2x-n 相当于将 x 左移一位然后擦掉所有 k 位的 1（1 \le x < n）。一直左移一直擦，总会有只剩一个 1 的时候，此时再回退（2x \leftarrow x）就归 1 了。综上，所有的 x 都与 1 连通。

得证。