ARC 201-300/ARC208C - Mod of XOR - 競技プログラミング用 知識集積所

---

問題

ARC208C

必要知識

簡単な内容は省略

• 考察問題

考え方

考察問題。

余りの条件があるということで、商をセットにして考える。

まず、最も単純な、商が0になる解があるパターンを考える。
この場合「c^n==xかつn>x」となればいい。
つまり、c^xを計算して、それがxより大きければ、それをnとするだけでよい。
（n<2^60は明らかに満たされる）

さて、この話はどういう入力に対して解決できたのかを考える。
c^xがxより大きいということは、cの最上位ビットによってxの同じ位置の値が0から1に変わったということである。
つまり、その条件は上の話を使って答えられるので、以後ではそのような入力ではないことを仮定してよい

cの最上位bitと同じ位置にxにもビットが立っているということは、xを2倍したら確実にcより大きい。
また、n>xであることから、nを2倍したらcより確実に大きい。
ということは、cをnで割った商は2より小さい。
そして商が0ではないという仮定があるので、商は1しかありえない。
つまり、「c^n==n+xかつn>x」となるしかない。

これは、下のビットから考えることで構成できる。
まず、cとxの立っている最下位ビットを見る。
位置が違う場合、より下にある方のビットが、nをどうやってもc^nとn+xで一致しない（ビットの値が両方変わるか両方変わらないかなので）ので不可能と判断できる。
同じ位置だった場合には、その位置の1つ上を見る。
1つ上のビットの中身が一致した場合には、そのビットには何もしなくてよい（実際にcやxからビットを消す）。
1つ上のビットの中身が異なった場合には、nのビットを立てることで、c^nからはビットをただ消し、n+xは繰り上げを行う（実際にcからビットを消し、xにはビットを足して繰り上げる）。
両者が同時に0になったらc^n==n+xとなるnの構成に成功している。
ただし、このままではn>xにならないので、nの十分高いビットを1つ立ててn>xにしておく。
（n<2^60は明らかに満たされる）

以上2通りを順に試し、見つかったらそれを、2つともダメなら-1を答えればよい。

解答例

解答例

注意点

別解

一発で構成する

実は商が1の場合の構成法、(c-x)/2で一発で出せるらしい。
公式解説参照（方針が全く違うように見えるが、実は同等）