考えたこと

xと2xが同一視されるのだから2で割れるだけ割った値で判断すれば良い

同値類の代表元

割る回数は30回程度なので余裕で間に合う

公式解説

あー、なるほど「既にでた数かどうか」の判定についての説明が足りなかった

数の個数は10^5程度だけど、値の範囲は10^9なので出現の有無を配列で持ちたくないというわけか

解説はしなかったが、自分は深く考えずにPythonのsetに入れてそう。これはハッシュテーブルなのでO(1)