yukicoder No.1243 約数加算
問題
整数A, Bが与えられ、Aに対して「正の約数を1つ選び、Aに足す」という操作を120回まで繰り返して、AとBが等しくなるようにしたい。
テストケースがT個与えられる。
各A, Bに対して、加える約数を列挙せよ。
制約
- 1 <= T <= 100
- 1 <= A_i < B_i <= 10^18
解法
A,Bが大きいのでまともに約数を列挙していては間に合わない。
そこで、簡単に大きな数字になりえる2のべき乗のみ考える。
(1～10^18の中で2のべき乗は59個程度しかない)
ある2のべき乗でAが割りきれるとき、2進数的に見ると、Aが「101001...0110000」のような場合、下位の「10000」の部分までになる。これを加えた場合、この1が次のビットに移動し、Aは「101001...1000000」のようになる。
これをBを超えない範囲で繰り返すと、上位の部分はBと同じ＆下位の部分が0になっているようなビット列にすることができる。
次に、下位の0の部分がBと一致するように加算したいが、10000に対して、1000や10などは約数になるので、上のビットからBでビットが立っているところの数値は約数になりえるため、そのまま足していけば良い。
ビットのサイズが60桁程度のため、上りと下りで120回以下に抑えられる。
反省
Bを超えない最大のものを選んでいくとき、2^iだけでなく、A/2^iも約数になるが、こっちの方を選んでしまうと、上記の操作よりも多くなってしまう。
