XOR Divisor Sugoroku

解説

この解説では、$x$ 自身を除く $x$ の約数を $x$ の 真の約数、$x$ 自身を除く $x$ の倍数を $x$ の 真の倍数 と呼びます。

各クエリについて $X$ から $1$ までの移動方法をすべて調べるのは困難です。そこで、すべての $x$ について、$x$ から $1$ まで移動したときに実現できる XOR の値をあらかじめ求めます。

移動を逆向きに考える

問題では、現在いる整数を $x$ とすると、$x$ の真の約数 $d$ へ移動できます。すなわち、

$$\ x\to d \qquad (d\mid x,\ d\<x)\$$

という移動が可能です。

これを逆向きに見ると、$d\to x$ と移動できるのは、$x$ が $d$ の真の倍数であるときです。したがって、整数 $d$ から移動できる整数は

$$\ 2d,3d,4d,\ldots\$$

です。

また、XOR は計算する順番を入れ替えても値が変わりません。したがって、

$$\ X\to\cdots\to1\$$

という経路を逆向きにした

$$\ 1\to\cdots\to X\$$

を考えても、経路上の $A_i$ の XOR は同じです。

よって、整数 $1$ から各整数 $x$ へ向かう方向に DP を行います。

DP の定義

$\mathrm{check}[x][v]$ を、

$1$ から $x$ まで真の倍数へ移動する経路のうち、経路上の整数に書かれた値の XOR を $v$ にできるものが存在するか

を表す bool 値とします。

$0\le A_i<64$ であるため、いくつ XOR を取っても値は $0$ 以上 $63$ 以下です。したがって、各 $x$ について考える必要がある $v$ は $64$ 通りだけです。

DP の初期値

$x=1$ のとき、通っている整数は $1$ だけなので、

$$\ \mathrm{check}[1][A\_1]=\mathrm{true}\$$

とします。それ以外の状態はすべて false で初期化します。

DP の遷移

整数 $x$ について、

$$\ \mathrm{check}[x][v]=\mathrm{true}\$$

であるとします。

$x$ の真の倍数 $y$ へ移動すると、新たに整数 $y$ を通るため、XOR に $A_y$ が追加されます。したがって、

$$\ \mathrm{check}[y][v\oplus A\_y]=\mathrm{true}\$$

と遷移できます。

$x$ の真の倍数は $2x,3x,4x,\ldots$ なので、実装では次のように列挙できます。

1
2
3
4
5
6
7
8
9for (int x = 1; x <= N; x++) {
    for (int y = 2 * x; y <= N; y += x) {
        for (int v = 0; v < 64; v++) {
            if (check[x][v]) {
                check[y][v ^ A[y]] = true;
            }
        }
    }
}

常に $x<y$ が成り立つため、$x$ の小さい順に処理すれば、遷移元の状態はすでに確定しています。

クエリへの回答

クエリ $(X,Y)$ を考えます。

$\mathrm{check}[X][v]=\mathrm{true}$ である $v$ は、$X$ から $1$ まで移動したときに実現できる XOR の値です。この経路を選んだときのスコアは

$$\ Y\oplus v\$$

です。

したがって、答えは

$$\ \min\_{\mathrm{check}[X][v]=\mathrm{true}}(Y\oplus v)\$$

です。

$v$ は $0$ 以上 $63$ 以下なので、各クエリについて $64$ 通りすべてを試せばよいです。

計算量

整数 $x$ からは、その真の倍数 $2x,3x,4x,\ldots$ へ遷移します。

したがって、倍数関係の総数は

$$\sum_{x=1}^{N}\left\lfloor\frac{N}{x}\right\rfloor$$

です。

これは調和級数の形であるため、DPの遷移の数は $O(N\log N)$ となります。

各遷移で $64$ 個の XOR 値を調べ、各クエリでも $64$ 個の値を調べるため、全体の時間計算量は$A_i$ が取りうる値の種類数 $\sigma = 64$ として $O(\sigma(N\log N+Q))$ です。