A Bangladeshi Contest at SUST（20151212）
UVa 13036
相異なるとは限らないフィボナッチ数の積で表される整数を興味深い数と呼ぶ．
フィボナッチ数は $1,2,3,5,8,13,\ldots$ であるので，
例えば，$100 = 2 \times 2 \times 5 \times 5$ は興味深い数である．
$A$ 以上 $B$ 以下の興味深い数のうち，もっとも大きい物を求める問題．
存在しないならそれを指摘する．
$B$ 以下で最大の興味深い数を求めれば良く，それが $A$ 未満なら存在しないと答えれば良い．
$10^{18}$ 以下の興味深い数はそこそこ多く全列挙すると間に合わないと思う．
そこで，半分全列挙した．
$2,3,5,7$ の積で書けるものを列挙し $x_1,x_2,\ldots$ とする．
また，$13,21,34,\ldots$ の積で書けるものも列挙し小さい順に $y_1,y_2,\ldots$．
（$8$ は $2^3$ なので考える必要はない）
そうすれば，興味深い数というのは，$x_i y_j$ と書けるものである．
そして，各 $x_i$ に対して，$B/x_i$ 以下で最大の $y_j$ を二分探索などで求めれば良い．
この部分を表示するには表示権限を持つユーザーでログインする必要があります．
Current time: 2024年04月20日00時26分49秒
Last modified: 2015年12月16日01時40分22秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151212_1
トップページに戻る
Logged in as: unknown user (not login)