Codeforces Round #782 (Div. 2) D. GCD Guess
https://codeforces.com/contest/1665/problem/D
問題概要：
インタラクティブ問題。
1≦x≦10^9なるxを当てる。
1以上2*10^9以下の2整数a,bをクエリ出力すると、gcd(x+a,x+b)が返ってくる。
30クエリ以内にxを当てよ。
自分の失敗方針：
以下、自分の考えた失敗方針。
xが2で何回割れるかを知ることを繰り返す作戦を考えた。
つまり、x=2^y*x'のyを求める。
これはa=2^29,b=2^30とすれば分かる。x'は奇数。
次に、x'に1を足して偶数にし、それが2で何回割れるか調べる。
a=2^y,b=2^y+2^29とすればよい。
これを繰り返す。
しかしこれだとあと一歩のところで求まらない、2^30を足さなければならない。
しかし2^30をたすと制約b≦2*10^9を超えてしまう。
正解方針：
正解方針は、xの各bitを調べるように考えること。
下のbitから決定することが可能。
第(i-1)bit(0-index)まで判明したら、それらを引いてから第ibitを調べる、と考える。
引く値をrとすると、負が許されるならa=-r,b=-r+2^(i+1)とすればよい。
返ってきた値が2^iなら第ibitは1と分かる。
しかし引き算はできないので、2^iを足してから引き算し、求めたbitを反転する。
すなわち、a=2^i-r,b=2^i-r+2^(i+1)とする。
自分の思考の癖を直すための、無理やり考察典型化：
「2進数で考える」
2で何度も割りたくなったら、無理やりにでも2進数のビットで考えられないか検討する、うまくいけば見通しが良くなる。
「一気に決められそうな時でも、1つずつ決めると簡単になることあり」
一気に割れる時でも(2^yのように)、一歩ずつにして考えることで単純化できないか確認する。
