SPOJ 23938 - Save the Scofield !! [UJ01]

Source

SPOJ 23938 [UJ01]

問題概要

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

テストケースの数 $T$ は $1 \leq T \leq 300000\ (3 \times 10^5)$ を満たす
$1 \leq A, B \leq 1000$
$1 \leq N \leq 1000000000\ (10^9)$

解法

答えに対して二分探索すれば良い．
$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: 2024年04月20日18時18分55秒
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)