Codeforces #184 Div2 B 「Continued Fractions」
問題
http://codeforces.com/contest/305/problem/B
訳
高さnのcontinued fractionとは次のような式である。
あなたに2つの有理数、p / qと、高さnのcontinued fractionが与えられる。この2つが同じ値かチェックせよ。
制約
1 <= p, q <= 10^18
1 <= n <= 90
1 <= a_i <= 10^18
考えた事
例えばn=3 a={1, 2, 4}で実際に計算してみると、a_3からa_1へと計算していけばよい。まずa_3=4は4 / 1である。a_2と計算する前に、分母と分子をひっくり返す!4 / 1 -> 1 / 4。それからa_2を通分して8 / 4とし、足し合わせる 1 / 4 + 8 / 4 = 9 / 4。a_1と計算する前に、分母と分子をひっくり返す!9 / 4 -> 4 / 9。それからa_1を通分して9 / 9とし、足し合わせる9 / 9 + 4 / 9 = 13 / 4。
ってなかんじで、何かしらの分数があるから、それをひっくり返す!通分する!足し合わせる!ひっくり返す!通分する!足し合わせる!ひっくりk(ryを繰り返していけばcontinued fractionの値がでる。ここで、足し合わせるときに、約分する必要はないのかということがある。まず、最初の分数は、1 / a_nであるが、これは既約分数である。既約分数と整数を足したときに出来る分数は、これまた既約分数である。と、いうわけで、約分する必要はない。さらに、通分したときに分母が10^18を越えた時点でそれ既約分数であり、p / qと同じにならないので即"NO"としてよいことになる。
コーナーケース
p / qは既約分数とは限らないぞ!
ソースコード
typedef long long int64; int64 gcd( int64 a, int64 b ){ if( a < b ) swap( a, b ); if( a % b == 0 ) return b; return gcd( b, a % b ); } int main() { // 入力 int64 P, Q, A[100]; int N; cin >> P >> Q >> N; for( int i = 0; i < N; i++ ){ cin >> A[i]; } // p / qを約分する int64 x = gcd( P, Q ); P /= x; Q /= x; int64 bunsi = A[N-1]; int64 bunbo = 1; for( int i = N - 2; i >= 0; i-- ){ // ひっくり返す! swap( bunsi, bunbo ); // 新しい分数の分子・分母が大きくなり過ぎないかチェック if( (double)bunbo * A[i] + bunsi > 1e18 ){ bunsi = bunbo = -1; break; } // 通分する! A[i] *= bunbo; // 足し合わせる! bunsi += A[i]; } // 答え合わせ bool ok = (bunsi == P && bunbo == Q); cout << (ok ? "YES" : "NO") << endl; }