【今日の反省会】Codeforces Global Round1（C問題解説付き）

今日も元気に反省しよう!!

ということで、今回の反省会は昨日のCodeforces Global Round1についてである。結果は2完で、A,B問題を最初の40分ぐらいで解いたのだが、その後C問題に残り全ての時間を費やしても全く解けなかった。なので、今回のテーマはそのC問題である。

Problem - C - Codeforces

この問題のキーポイントは、次の定理である。

A^B = A+B - 2(A&B)

ここに^はビットごとのXOR演算、&はビットごとのAND演算である（はてなブログのtex記法ではアンパサンドが使えないので普通に書いた。見苦しくてごめんなさい）。

まあ反省と言えば、いろはすがこの定理を知らなかったことであろうか。今覚えた。

あと考察力が足りなかった部分もあるが、これはもう演習で鍛えていくしかないであろう。

そんなわけで、今回は珍しく反省が短く終わってしまったので、残りは誰得のC問題の解説でもしようかと思う。 [まあ一番は自分のためだが、ひょっとしたら誰かの役に立つかもしれないので。]

C問題解説

まずは、先程の定理を証明しようと思う。

〜上の定理の証明〜

$A=\sum_{i=0}^\infty a_i 2^i$

$B=\sum_{i=0}^\infty b_i 2^i$

とする。ここで、

A&B = $\sum_{i=0}^\infty ((a_i + b_i)/2)2^i$

A^B = $\sum_{i=0}^\infty ((a_i + b_i)\%2)2^i$

[ただし、%は剰余、/は商の小数点以下を切り捨てたものを表す]であるから、

2(A&B) + A^B = $\sum_{i=0}^\infty (2(a_i + b_i)/2 + (a_i + b_i)\%2)2^i$

商と剰余の定義から、

2(A&B) + A^B = $\sum_{i=0}^\infty (a_i + b_i)2^i$ = A+B.

これより定理を得る。

〜証明終〜

さて、これを使って問題を解いていこう。まず、Aを2進数表記したときの桁数をnとおこう。ここで、(i)1桁目〜n桁目までのどこかに0がある場合、(ii)そうでない場合で場合分けする。

(i)1桁目〜n桁目までのどこかに0がある場合

Aをビット反転したものをBとすれば、場合分けの条件より0<B<Aであり、

A^B = 11...1

A&B = 00...0

であるから、

gcd(A^B, A&B) = 11...1.

(ii)そうでない場合

この場合は、Aをビット反転したものは0だから、条件0<B<Aを満たさないためこれは解にならないことに注意する。

このとき、任意のB<Aについて、

A&B = B

である。また、先程の定理を用いれば

A^B = A+B - 2B = A-B

と分かる。そこで、問題は

$gcd(A-B,B)$

の最大値を求めることになるが、

$gcd(A-B,B)=gcd(A,B)$

なので、結局 $gcd(A,B)$ を最大化する問題になる。 0<B<Aなので、最大値は明らかにAの二番目に大きな（つまり、Aの次に大きな）約数である。これは、単純な線形探索でAの二番目に小さな（つまり、1の次に小さな）約数を求めてそれでAを割ればよい。 Aの上界は10⁷程度のオーダーなので、1からAまで全て走査していたのでは間に合わないが、実際には $\sqrt{A}$ まで走査すればよいので間に合う（ $\sqrt{A}$ まで走査して見つからなければAは素数）。