A and B - Educational Codeforces Round 78 div2 b
#math
editorialの補足
a ≥ bとする
xの条件
1.
2. と(a - b)の2で割った余りが等しい
上2つを満たす最小の自然数をxとする
a, bが等しくなる足し方
をa, bに分配する
とりあえず, a, bにずつ分配する
a, bが等しくなるのだから, 結局
aにはを足し,
bにはを足す
計算の途中で小数が出ないようにする
xの性質2. よりbに足すのは
xの見つけ方
残る問題は, 1., 2. 両方を満たすxが見つかるのかという問題
1. に関しては二分探索で求める
求めたxを1ずつ増やしたとき, の偶奇はすぐ変わるか
時間計算量の話
ポイントは, x(x + 1)の約数に2が2つ以上あるか
すなわち4の倍数か
一方は奇数
もう一方が4の倍数かは, 2の倍数に関して1回おき
よって時間計算量は大丈夫
