01 Shift Xor

解答

数を多項式としてみなすことを考えましょう。

具体的には、ある数$X$を二進数表記をしたとき,$k$ビット目が立っている時に$x^k$を要素にもつような 全ての係数が$\{0, 1\}$の多項式を対応させます。

たとえば、 $13 = 2^3 + 2^2 + 1$ですので$13 \rightarrow x^3 + x^2 + 1$となります。

加えていくつかの定義をします。

---

はじめに、$2$つの整数係数多項式$f(x), g(x)$が全ての係数において偶奇が等しいとき これらは「互いに法を$2$として合同である」とし、「$f(x) = g(x) (mod\ 2)$」とかくことにします。

たとえば、

$f(x) = x^4 + x^2 + 1, g(x) = 19x^4 -x^2 + 101$

は互いに法を$2$として合同で$「f(x) = g(x) (mod\ 2)」$です。

$2$つめに、多項式$f(x), g(x)$に対して、以下を満たす整数係数多項式$q(x)$が存在する場合、「$f(x)$は$g(x)$で割り切れる/$g(x)$は$f(x)$の因数である」ということにします。

・$f(x) = g(x)q(x) (mod\ 2)$

たとえば、

$f(x) = x^2 + 1, g(x) = x + 1$

としたとき

$f(x) = x^2 + 2x + 1 = g(x)g(x) (mod\ 2)$ですので「$f(x)$は$g(x)$で割り切れる/$g(x)$は$f(x)$の因数」です。

ここで、$A_i$を上記の規則に従って多項式に対応させた結果得られる多項式を$f_i(x)$とします。

$3$つめに、整数係数の多項式の集合を$G$とし、$G$に属する多項式のうち、以下を満たす$(c_1(x), ... c_n(x))$が存在する多項式$h(x)$の集合を$H$とします。

$・h(x) = \displaystyle \sum_{i = 1}^{n} {c_i(x)f_i(x)} (mod\ 2) , c_i \in G　かつ全ての係数が{0, 1}のいずれか$

---

明らかに、題意の操作を繰り返して得られる数を多項式に変換した時、それらは$H$に含まれるものであることがわかります。

そして、全ての$f_i(x)$を割り切る多項式のうち、全ての係数が$\{0, 1\}$になるものが存在します。

これを$P$とし、これが$1$以外に存在しないことが必要十分条件でもあります。($P(x) = 1$が条件を満たすことは明らか。）

このような$P$を求めるには、多項式に対して通常の整数と同様に$Euclid$の互助法的な考え方をもちいて再帰的に計算を行えば良いです。

適切に実装を行えば、時間計算量$O(N(logA)^2)$の回答を得ることができます。