ibeckuuの日記

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第88回「永遠に続くビリヤード」

CodeIQ

CodeIQというサイトで問題に挑戦した記録です。

問題文を要約すると下記の通り、

ビリヤードについて考える。クッションに対して45度の角度にボールを打つとする。
ボールの勢いが十分強くクッションに反射して同じ場所を繰り返して動くものとする。
横にm個、縦にn個のマス目で任意の格子点から始め、通過したマス目の数をカウントする。
標準入力からm,nが与えられた時、通過するマス目の数の最小と最大を解答する。
m,nはいずれも60以下の整数

方針

通過するマス目の数は下記の通り計算できる。

${m=1,n=1}$ のとき
最小、最大とも ${1}$
${m},{n}$ の最大公約数が ${1}$ 以外のとき
最小は ${\frac{m \times n}{ \gcd (m,n)}}$
最大は ${\frac{m \times n \times 2} { \gcd (m,n)}}$
${m},{n}$ の最大公約数が ${1} \Leftrightarrow m,n$ が互いに素のとき
最小、最大とも ${m \times n}$

上記の説明

${m=1,n=1}$ のときは最小、最大ともに ${1}$ である。

次に、 ${m=n (m,n \geq 2)}$ のとき、

最小は ${m (=n)}$

f:id:ibeckuu:20160413013337j:plain

最大は ${2 \times m (=2 \times n)}$ である。

f:id:ibeckuu:20160413013629j:plain

${m,n}$ のいずれかがもう片方の倍数になっている場合、

仮に ${m = k \times n}$ とすると、

最小は ${m}$

f:id:ibeckuu:20160413035531j:plain

最大は ${2m}$

f:id:ibeckuu:20160413032637j:plain

上記の他で最大公約数が1でない場合、

最小は ${\frac{m \times n}{ \gcd (m,n)}}$

f:id:ibeckuu:20160413033118j:plain

最大は ${\frac{m \times n \times 2} { \gcd (m,n)}}$

f:id:ibeckuu:20160413033325j:plain

互いに素のとき、

最小、最大とも ${m \times n}$

f:id:ibeckuu:20160413033530j:plain

実装

上記を利用して提出したコード (Ruby)

では、

Sponsored Link