SPOJ 23938 - Save the Scofield !! [UJ01]

Source

SPOJ 23938 [UJ01]

問題概要

正整数 $A,B,N$ が与えられるので,$A$ または $B$ の(少なくてもどちらか一方の)倍数に該当する正整数のうち,小さい方から $N$ 番目のものを求める問題.

解法

答えに対して二分探索すれば良い.
$x$ 以下の $A$ または $B$ の倍数の個数は,包除原理により,$\lfloor x/A \rfloor + \lfloor x/B \rfloor - \lfloor x/{\rm LCM}(A,B) \rfloor$ である.
それで十分だが,$A$ または $B$ の倍数の分布は周期 ${\rm LCM}(A,B)$ で,$[1, {\rm LCM}(A,B)]$ には,該当する倍数は $c := {\rm LCM}(A,B)/A + {\rm LCM}(A,B)/B - 1$ 個あるので,$\lceil N/c \rceil$ 周期分は無視して考えて,残りの部分だけ二分探索すると $64$ ビット整数の割り算などがほとんど必要なくなって,二分探索の範囲も狭くなって速くなる.

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

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


Current time: 2017年09月22日15時19分13秒
Last modified: 2017年06月19日05時04分27秒 (by laycrs)
Tags: Competitive_Programming Sphere_Online_Judge SPOJ_Classical
トップページに戻る

Logged in as: unknown user (not login)

ログイン: