CF1665D GCD Guess

个人思路：
\(\gcd(x+a,x+b) = gcd(x+a,b-a)\)。

考虑固定 \(a\)，然后试出来 \(x+a\) 所有因子。
然后发现质数根本试不完。

发现询问 \(30\) 次，\(2^{30}\) 刚好比 \(x\) 大一点。

考虑 \(2\) 进制拆分，从低往高，依次去试每一位：
第 \(i\) 次，我们需要判断第 \(i\) 位，是 \(0\) 还是 \(1\)。由于我们知道 \(x\) 的 \(1\sim i-1\) 位，我们可以让 \(x+a\) 为 \(2^{i-1}\) 次方的倍数，让 \(b-a = 2^i\)。通过 \(gcd(x+a,2^i)\) 来判断第 \(i\) 位的情况，如果返回值为 \(2^{i-1}\)，则第 \(i\) 位为 \(1\)，返回值为 \(2^i\)，则第 \(i\) 位为 \(0\)。不难发现，\(a\le2^{i-1},b-a=2^i,b\le2^i+2^{i-1}\)。因为 \(x < 2^{30}\)，所以只用判断前 \(30\) 位，\(a,b \le 2^{30}+2^{29} < 2\times 10^9\)，刚好满足题目要求。

那么 \(a\) 具体是多少呢？我们初始令 \(a=1\)，因为题目要求 \(1\le a,b\le 2\times 10^9\)，然后如果 \(x+a\) 的第 \(i\) 位是 \(1\)，我们让 \(a \leftarrow a + 2^{i-1}\)，这样判断第 \(i+1\) 位时，\(x+a\) 就是 \(2^i\) 的倍数了。

可能是实现时的问题，我的代码必须要开 long long 才能过。