最初、「これは本当に AGC か！？？」となってた

問題へのリンク

問題概要

$A$ 以上 $B$ 以下の整数の中からいくつか選んで、OR 和をとってできる値が何通りあるか求めよ。

制約

$1 \le A \le B \lt 2^{60}$

考えたこと

一見するとこどふぉっぽい見た目の問題だけど、実はすごく AGC っぽい感じの問題だった。

とりあえず、最上位桁から見て行って、 $A$ と $B$ とで一致しているところは無視できるので、全部 $0$ にしてしまって除外しておこう。そうすると、ある桁 $d$ が存在して

$B$ の $d$ 桁目は $1$ (B にとっての最上位桁)
$A$ の $d$ 桁目は $0$

という状態にできる。よって、次の場合分けがしたくなる。

OR 和の $d$ 桁目が $0$ の場合 ( $A$ 〜 $2^{d} - 1$ の場合に帰着)
OR 和の $d$ 桁目が $1$ の場合 ( $A$ から $B$ までフルに使える)

このように場合分けすると、いかにも再帰的に解くような流れになっていきそうで、こどふぉ感を最初感じた。

d 桁目が 0 のとき

まずは OR 和の $d$ 桁目が $0$ の場合を考えてみる。この場合は

$A, A+1, A+2, \dots, 2^{d}-1$

の OR 和で作られる数を求めたい。そして当然ながら、

$A, A+1, A+2, \dots, 2^{d}-1$

はすべて作れる！！そしてよくよく考えると、これらの数以外は作れない。なぜなら、一般に整数 $v$ に対して他の正の整数 $x$ と OR をとると

$v$ OR $x \ge v$

が成立するからだ。つまり、 $A, A+1, \dots, 2^{d}-1$ からいくつか選んだ OR 和が $A$ 未満になることはありえない。一方、 $d$ 桁目が 1 になることもないので、作れる数は $A$ 以上 $2^{d}-1$ 以下の整数ということで確定する。

d 桁目が 1 のとき

$d$ 桁目が 1 であるようなものを少なくとも 1 つ以上含めないとダブルカウントになってしまうので注意が必要そう。でも、 $A$ 以上 $B$ 以下の整数の中に、 $2^{d}$ ( $d-1$ 桁目までがすべて 0) が含まれるので、そんなに心配しなくて大丈夫。

問題は $C = B - 2^{d}$ としたとき、

$A$ 以上 $2^{d}-1$ 以下の整数
$0$ 以上 $C$ 以下の整数

を使って作られる整数をすべて求める問題となる。 $C$ の最高位の桁を $e$ とすると、さっきと同じ理屈から、

$A$ 以上 $2^{d}-1$ 以下の整数からは、 $A$ 以上 $2^{d}-1$ 以下の整数がすべて作れる
$0$ 以上 $C$ 以下の整数からは、 $0$ 以上 $2^{e+1}-1$ ( $= D$ とする) 以下の整数がすべて作れる

ということになる。前者の値と後者の値の OR 和も考えないといけないが、それは完全に前者に含まれる。よって、

$A \le D$ のときは、 $2^{d}$ 個がすべて作れる
$A \gt D$ のときは、 $2^{d} - A + D$ 個が作れる

ということになる。

コード

以上をまとめると、 $O(\log B)$ で解ける。

#include <bits/stdc++.h>
using namespace std;

long long solve(long long A, long long B) {
    if (A == B) return 1;
    int d = 61;
    for (; d >= 0; --d) {
        if ((B & (1LL<<d)) && !(A & (1LL<<d))) break;
        A &= ~(1LL<<d);
        B &= ~(1LL<<d);
    }

    long long zero = (1LL<<d) - A; // d 桁目が 0
    int d2 = d-1;
    for (; d2 >= 0; --d2) if (B & (1LL<<d2)) break;

    long long ue = 1LL<<(d2+1);
    long long one = 0;
    if (A <= ue) one = (1LL<<d);
    else one = (1LL<<d) - A + ue;
    return zero + one;
}

int main() {
    long long A, B;
    cin >> A >> B;
    cout << solve(A, B) << endl;
}