<-- home

AtCoder ABC 121 D

March 22, 2020

https://atcoder.jp/contests/abc121/tasks/abc121_d

「解説」と違う方針で解いたのでメモ。

を求めるとき、を2進数で表したときの桁目は、排他的論理和が各桁ごとに独立に計算できることから、それぞれの桁目から計算できる。 そこで、の桁目が0であるものがn個, 1であるものがm個とすると、排他的論理和が交換法則を満たすことに着目して、の桁目はとなる。

であるから、

となる。

0から順に2進数で書いてみると、

0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0 1 0 1 1
0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 1 1 0 1
0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 1 0 0 0 0

となるので、桁目は、0が個、1がというパターンが繰り返されることがわかる。したがって、0からある2進数の桁目に1が何個あるかはで求められる。これを用いれば、の桁目に1が何個あるかもで求められる。 したがって、の0桁目から順に求めて、O(max(Aの桁数, Bの桁数))で答えが計算できる。

#define N_DIGIT 40
i64 A, B;

int main() {
    cin >> A >> B;
    if (A == B) {
        cout << A << endl;
        return 0;
    }

    i64 ans = 0;
    i64 p = 1;
    auto f = [&](i64 x, i64 p, i64 n) {
        // [0, x) のn桁目に1が何個あるか
        i64 k = x / p;
        if ((x >> n) & 1) {
            return (k / 2) * p + x % p;
        } else {
            return (k / 2) * p;
        }
    };

    REP(i, N_DIGIT + 1) {
        i64 n_one = f(B + 1, p, i) - f(A, p, i);
        ans += (n_one % 2) * p;
        p *= 2;
    }
    cout << ans << endl;

    return 0;
}