pythonのfractions moduleで殴るだけの問題。rubyやhaskellでもよい。 友人はまじめに解いてて(ratingが絡まない練習会だったので)えらいなあと思った。

B. Continued Fractions

問題

有理数$\frac{p}{q}$と連分数$[a_1;a_2;\dots;a_n]$が与えられる。 これらが等しいか答えよ。

解法

適当な言語の有理数型を用いて計算すればよい。やるだけ。

まじめに計算するには、$\frac{p}{q}$を連分数展開し一致するか見る。 有理数$r$を、整数$n$と有理数$r’$を用いて$n + \frac{1}{r’}$と表現しなおす、という操作を再帰的に行う。 連分数を畳み込む方向で計算するとoverflowしてしまう。

実装

#!/usr/bin/env python3
import fractions
p, q = map(int,input().split())
n = int(input())
a = list(map(int,input().split()))
y = fractions.Fraction(p, q)
x = fractions.Fraction(0)
for it in reversed(a):
    if x != 0:
        x = 1 / x
    x += it
print(['NO','YES'][x == y])