SRM429 Div1 500
問題
N種類の飲料によるカクテルがある。しかし、それぞれの飲料の割合を忘れてしまった。
メモには、N-1個の組み合わせについて、2組の飲料の配合比が書かれている。
メモを頼りに、元のN種類全部の配合比を求める。ただし配合比は最小の比率になる整数値。
例えば、3種類の場合、A:B=9:8でB:C=9:8ならば、A:B:C=81:72:64になる。(162:144:128みたいなのはダメ)
考え方
小数で各飲料の配合比を求める場合を考える。
1つ目を1.0とすると、例ではA:B=9:8なので、A=1.0ならB=0.888...となる。そして、Bがわかるので、Cも0.888...*8/9=0.790...となる。したがって、1.0:0.888...:0.79...という配合比が得られる。
まだ計算していない飲料はdfsで探して計算する。
しかし、これではこの比になる整数比がわからない。
(ちなみに、全部に同じ整数値を掛けて、各要素が整数値になるかを確かめる方法では、整数値が10^9を超えるパターンがあるためTLEになる)
そこで、有理数(q/p)で計算する方法を考える。
上記の計算を小数ではなく有理数で計算すると(1/1):(8/9):(64/81)となる。
すべての分母の最小公倍数をすべてにかけることで整数比にすることができる。
さらに、すべての分子の最大公約数ですべてを割ると最小の整数比を求めることができる。
(分数の状態で約分したり、最後に最大公約数で割ることをわすれない)
(分数はpair
