同时我们知道 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 的这一位是 0,x 这一位也只能是 0。如果 y 的这一位是 1,则 x 这一位可以是 0 也可以是 1。
在此基础上,我们还要满足 y \bmod x = y - x。这个怎么实现?考虑 y 的二进制下的最高位,若 x 这一位也为 1,则一定满足。若 x 这一位为 0,此时必须有 y < 2x,那么 x 的下一位必定是 1。而根据刚才我们的结论,x 某一位是 1 时 y 必须也是 1,则 y 的这一位是 1,则 x 再下一位也是 1……以此类推。推到最后我们发现无法满足条件,所以 x 这一位不可能是 0。
剩下的实现很简单,数位 DP 即可。
需要注意的是这个数位 DP 不能像常规数位 DP 那样拆成 [1, L - 1] 和 [1, R] 分开计算,因为这样无法统计 x 在 [1, L - 1] 而 y 不在时的贡献。所以必须在 DP 时同时记录上下界。