新入生プログラマーコンテスト昼の部和差算解説

最近全然記事出しませんでしたね、そもそも見てる人そんなにいないと思いますが。
#解説
なんか燃えてそうで怖いです。裏側等は後日談として書きたいと思います。
星2~2.5ありそうなので2と2.5どっちがいいかアンケート取ったら1.5になりました。(?)
##問題リンク
https://yukicoder.me/problems/5050
##解法
$N\le10^{18}$ なので、全探索では間に合いません。
少し探索すると、
$p=a_0,q=b_0$ としたとき、
$a_1=p-q,b_1=p+q$
$a_2=-2q,b_2=2p$
$a_3=-2p-2q,b_3=2p-2q$
$a_4=-4p,b_4=-4q$
$a_5=-4p+4q,b_5=-4p-4q$
$a_6=8q,b_6=-8p$
$a_7=8p+8q,b_7=-8p+8q$
$a_8=16p,b_8=16q$
となります。よって、 $a_{8i+j}+b_{8i+j}$ の最大値は $a_j+b_j$ の最大値の $16^i$ 倍になります。
これにより、それぞれの $a_N,b_N$ を求めることができます。
また、最大値になりうる場合は、
$p=A,q=C$
$p=B,q=C$
$p=A,q=D$
$p=B,q=D$
の4つのみです。そのため、計算量は $O(log(N))$ で済みます。
##想定解
C++14:https://yukicoder.me/submissions/633118
PyPy3(Python3):https://yukicoder.me/submissions/633191
#終わりに
夜の部でも1問作問しているので是非解いてください！
最後まで読んでくださりありがとうございました。