mayoko’s diary

プロコンとかいろいろ。

SRM 543 div1 easy: EllysXors

問題

TopCoder Statistics - Problem Statement

L から R までの xor を取った整数の値を求めよ。

解法

各桁ごとに bit が立っているかを調べます。
2^i の桁が立っているかどうかを調べる時は, i 桁目の bit は 2^(i+1) 周期ごとに現れたり消えたりすることに着目すれば良いです。

別解ですが 4*n, 4*n+1, 4*n+2, 4*n+3 で bit が 0 になることを利用するのが一番賢そうです。

ll cnt(ll x, ll div) {
    ll p = x/(2*div), q = x%(2*div);
    ll ret = p*div;
    ret += (q>=div ? q-div+1 : 0);
    return ret;
}

class EllysXors {
public:
    long long getXor(long long L, long long R) {
        ll ret = 0;
        for (int i = 0; i <= 32; i++) {
            ll c = cnt(R, 1ll<<i) - cnt(L-1, 1ll<<i);
            if (c%2) ret |= 1ll<<i;
        }
        return ret;
    }
};