UVa 13036 - Birthday Gift to SJ - 2

Source

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$ を二分探索などで求めれば良い.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年11月18日11時33分53秒
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)

ログイン: