0%

HDU 5912 Fraction 题解

题目大意

模拟一个连分数的计算。

题解

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 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;
}