AtCoder, ABC121: D. XOR World

atcoder.jp

非常に大きな数（になりうる）２数 $A, B (A < B)$ が与えられます．
このときに， $F(A, B)$ を求める問題です．
ここで， $F(A, B)$ とは $F(A, B) = A \oplus A+1 \oplus A+2 \oplus ... \oplus B$ のように定義される関数です（ここで， $\oplus$ は排他的論理和を表します）．
$A$ が小さな値であり $B$ が非常に大きな数である場合，愚直に繰り返し計算をすると現実的な時間で計算ができません．
ここで， $F(A, B)$ をじっと眺めると（嘘: 私は解説を読みました）， $F(A, B)$ は $F(0, A-1) \oplus F(0, B)$ のように分解できることがわかります．
これについては解説を読んだだけではわからなかったのですが，実際に書き下してみると「なるほど！」となります．

これにより， $F(0, k)$ を効率的に計算できれば良いということがわかりました．
では，これを求めるアルゴリズムを考えましょう．
連続する２数 $t, t+1$ の排他的論理和は，

$t \oplus t+1 = \{ \begin{array}{l} 1 & \text{(if t が偶数)} \\ 2 & \text{(if t が奇数)} \\ \end{array}$

となります（実際に２進数で試してみてください）．
実際にはどちらか一方を利用するととで問題は解けます．
ここでは， $t$ が偶数の時の結果を利用します．

$F(0, A)$ は２数 $i, j$ を用いて $F(0, A) = i \oplus j$ のように表せます．
$i, j$ は以下のように定義できます．

$i = \{ \begin{array} 0 & \text{(if A+1を2で割ったとき商が偶数)} \\ 1 & \text{(if A+1を2で割ったとき商が奇数)} \\ \end{array}$

$j = \{ \begin{array} 0 & \text{(if A+1が偶数)} \\ A & \text{(if A+1が奇数)} \\ \end{array}$

考え方としては以下ようになります．

$[0, A$ ] の数列を [t, t+1] でくくり，くくれた部分を $0$ とみなし， $0 \oplus 0 \oplus \dots \0$ を考える
$A$ が綺麗にくくり出せない場合，前の処理で得られた数と $A$ との排他的論理和をとる

コードは↓

#include <iostream>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

long long f(long long a) {
    long long t, s;

    if (((a+1)/2)%2 == 0) t = 0;
    else t = 1;
   
    if ((a+1)%2 == 0) s = 0;
    else s = a;

    return t ^ s;
}


int main() {
    long long a, b; cin >> a >> b;
    cout << (f(a-1) ^ f(b)) << endl;
    return 0;
}