No.451

$a_1$ を適当に決めて $a_2$ 以降を計算する.

このとき,

$$a_2 = b_1 - a_1 = c_1 - a_1 \\ a_3 = a_2 - b_2 = c_2 - a_1 \\ a_4 = b_3 - a_3 = c_3 + a_1 \\ a_5 = a_4 - b_4 = c_4 + a_1 \\ a_6 = b_4 - a_4 = c_5 - a_1 \\ \vdots$$

となる. ただし, $c_i$ は $b_j$ ($j \leq i$) を適当に加減してできる数である.

このように, $i = 2,3,6,7,10,11,\dots$ のときは $a_1$ の項はマイナスとなり, そうでないときはプラスになる.

$i = 2,3,6,7,10,11,\dots$ のときに $a_i < 1$ となる項が現れたならば $a_1$ は大きすぎであり, $a_i > 10^{18}$ の項が現れたならば $a_1$ は小さすぎであるということになる. $i$ がそれ以外のときは逆になる.

あとは二分探索で $a_1$ を求めればいい.