SRM427 Div2 500

問題

ある惑星の宇宙人がカレンダーを作る。一日がdayLengthの長さで、一年はyearLengthの長さである。この長さはそれぞれ、その惑星が一回りする長さ、太陽を一周する長さである。しかし、通常、dayLengthの整数倍が一年とはならない。これを閏年を用いて調整する。閏年は一年の長さが普通の年より1日だけ長い年である。何年に一度閏年をいれなければいけないか。

考え方

解説とは違った感じで。(解法怪しいかも)
サンプルから、a=yearLength/dayLengthとb=yearLength%dayLengthとすると、a*dayLength+b==yearLengthとなる。すなわち、1年ごとにbの長さだけずれていく。
m年たったとき、この余分なb*mがdayLengthで割り切れれば、ずれを調整することができる。最小のmを求めたいので、b*m==lcm(b,dayLength)となればいいので、m=lcm(b,datLength)/bが答えになる。

反省

この方法のときは、b==0(ずれがない)ときは1を返すようにしておかないと、lcm(gcd)で例外処理をしてない場合は計算がおかしくなる。桁あふれに注意。