HDU 5912 Fraction 题解

题目大意

模拟一个连分数的计算。

题解

从后往前，设当前存的分数为 \(\displaystyle\frac{B}{A}\)，则更新后的分数为 \(\displaystyle\frac{A\cdot b_i}{B+A\cdot a_i}\)，一路递推即可。

代码

// https://vjudge.net/problem/HDU-5912
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;
typedef long long ll;
 
template <typename _Tp>
void read(_Tp &a, char c = 0, int f = 1) {
    for(c = getchar(); !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar()); a *= f;
}
 
template <typename _Tp>
void write(_Tp a) {
    if(a < 0) putchar('-'), a = -a;
    if(a > 9) write(a / 10); putchar(a % 10 + '0');
}

const int N = 15;

int n, a[N], b[N];

int main() {
    // freopen("0725_2.in", "r", stdin);
    int T;
    read(T);
    for(int _T = 1; _T <= T; _T++) {
        read(n);
        for(int i = 1; i <= n; i++) read(a[i]);
        for(int i = 1; i <= n; i++) read(b[i]);
        int A = 1, B = 0;
        int _A, _B;
        for(int i = n; i >= 1; i--) {
            _A = B + A * a[i];
            _B = A * b[i];
            A = _A;
            B = _B;
        }
        int g = __gcd(A, B);
        printf("Case #%d: %d %d\n", _T, B / g, A / g);
    }
    return 0;
}