2007 JOI本選-5-モービル

解法が大体思いついてからすぐだった

解法

この問題は、

安定しているモービルの両端にかかっている重さを両方k倍しても、
モービルは安定する

ということに注目してやると簡単

左の重さをrt,右の重さをbtとする

ここでrt,btは

「下にある部分的なモービルが安定するモービル全体の最小の重さ」

である

下にあるものが錘である場合は1とすれば良い

左側の重さをm倍、右側の重さをn倍すれば、モービルが安定するとすると

rt * m * p = bt * n * q
(mとnは互いに素)

という等式が成り立ち

(rt * p) / (bt * q) = n / m

となる。mとnは互いに素なので左辺を約分しきった状態が右辺であるので

(rt * p) と (bt * q)の最小公倍数をgとすると

n = rt * p / g
m = bt * q / g

よって左の重さは

rt * n

右の重さは

bt * m

となるので、その棒の重さが求められる

あとは再帰するだけ

(僕のコード)https://joi2007ho.contest.atcoder.jp/submissions/1983911

こんな感じかな