WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #184 Div2 B 「Continued Fractions」

問題

http://codeforces.com/contest/305/problem/B

高さnのcontinued fractionとは次のような式である。
f:id:Ekaing:20130525004624j:plain

あなたに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;
}