Codeforces 305B

こどふぉす 過去問

問題

n個まで連分数展開されたa0+1/(a1+1/...)の配列aと、分数p/qが与えられる。
この連分数展開されたものと分数p/qが等しいかどうかを返す。

1<=q<=p<=10^18
1<=n<=90

考え方

多倍長があれば、それを使って連分数をpp/qq形式に直して、pp*q == qq*pかどうかを判定。


または、p/qが連分数展開のa0,a1,...を選んで最後まで満たせるかどうかをチェック。

反省

多倍長で、かけ算をintしか用意していなくて、longlongを掛ける時にキャストしておかしくなった。