题解:AT_abc138_f [ABC138F] Coincidence

· · 题解

因为有 x \le y,则 y \bmod x \ge y - x

同时我们知道 y - x \ge x \oplus y,因此显然有 y \bmod x = y - x = x \oplus y

考虑如何满足 y - x = x \oplus y。先拆位,对于任意一位,一定有 y - x \le x \oplus y。只要任意一位没有取等,最后也一定取不到等。

所以对于任何一个二进制位,一定有 y - x = x \oplus y。那么如果 y 的这一位是 0x 这一位也只能是 0。如果 y 的这一位是 1,则 x 这一位可以是 0 也可以是 1

在此基础上,我们还要满足 y \bmod x = y - x。这个怎么实现?考虑 y 的二进制下的最高位,若 x 这一位也为 1,则一定满足。若 x 这一位为 0,此时必须有 y < 2x,那么 x 的下一位必定是 1。而根据刚才我们的结论,x 某一位是 1y 必须也是 1,则 y 的这一位是 1,则 x 再下一位也是 1……以此类推。推到最后我们发现无法满足条件,所以 x 这一位不可能是 0

剩下的实现很简单,数位 DP 即可。

需要注意的是这个数位 DP 不能像常规数位 DP 那样拆成 [1, L - 1][1, R] 分开计算,因为这样无法统计 x[1, L - 1]y 不在时的贡献。所以必须在 DP 时同时记录上下界。

code