任意门：http://codeforces.com/gym/100641/attachments
Con + tin/(ued + Frac/tions)
- Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
- Total Submission(s): 217 Accepted Submission(s): 27
The (simple) continued fraction representation of a real number r is an expression obtained by an iterative process of representing r as a sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer part and another reciprocal, and so on. In other words, a continued fraction representation of r is of the form
where a0, a1, a2, ... are integers and a1, a2, ... > 0. We call the ai-values partial quotients. For example, in the continued fraction representation of 5.4 the partial quotients are a0 = 5, a1 = 2, and a2 = 2. This representation of a real number has several applications in theory and practice.
While irrational numbers like √2 (sqrt(2)) require an infinite set of partial quotients, any rational number can be written as a continued fraction with a unique, finite set of partial quotients (where the last partial quotient is never 1 in order to preserve uniqueness). Given two rational numbers in continued fraction representation, your task is to perform the four elementary arithmetic operations on these numbers and display the result in continued fraction representation.
Each test case consists of three lines. The first line contains two integers n1 and n2, 1 ≤ ni ≤ 9 specifying the number of partial quotients of two rational numbers r1 and r2. The second line contains the partial quotients of r1 and the third line contains the partial quotients of r2. The partial quotients satisfy |a0| ≤ 10 and 0 < ai ≤ 10, the last partial quotient will never be 1, and r2 is non-zero. A line containing two 0's will terminate input.
For each test case, display the case number followed by the continued fraction representation of r1 + r2, r1- r2, r1×r2, and r1/r2 in order, each on a separate line. Use 64-bit integers for all of your calculations (long long in C++ and long in Java).
4 3
5 1 1 2
5 2 2
0 0
Case 1:
11
0 5
30 4 6
1 27
题意概括：
给一串 a 按照连分数定义算出 r1；给一串 b 按照连分数定义算出 r2;
最后按照连分数的格式 输出 r1 + r2, r1- r2, r1 * r2, r1 / r2;
解题思路：
模拟一遍连分数计算过程算出 r1 和 r2;
然后判断 r1 r2 是分数还是整数（因为是 LL ,作除法时对精度有要求)
模拟求连分数的逆过程输出 r1 r2 四则运算的结果。
AC code：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#define LL long long
using namespace std;
const int MAXN = ;
LL x1, x2, y, y2;
LL A[MAXN], B[MAXN];
int N, M; LL Gcd(LL a, LL b)
{
if(b == ) return a;
return Gcd(b, a%b);
} void solve1() //求 r1 分数
{
LL t = ;
x1 = , y = A[N-];
for(int i = N-; i > ; i--){
x1 = x1+A[i]*y;
t = y;
y = x1;
x1 = t;
}
x1 = x1+A[]*y;
} void solve2() //求 r2 分数
{
LL t = ;
x2 = , y2 = B[M-];
for(int i = M-; i > ; i--){
x2 = x2+B[i]*y2;
t = y2;
y2 = x2;
x2 = t;
}
x2 = x2+B[]*y2;
} void ppt(LL a, LL b) //输出连续分式（求分数的逆过程）
{
LL gg = Gcd(a, b);
a /= gg;
b /= gg;
if(b < ){ //分母小于零时，模不小于零
a*=-;
b*=-;
}
LL tmp = (a%b+b)%b; //小数部分
LL a0 = (a-tmp) / b; //整数部分
printf("%lld", a0);
a = tmp; //处理剩下的小数部分 swap(a, b); //分子分母倒置
while(b){
tmp = a/b;
printf(" %lld", tmp);
a=a%b;
swap(a, b);
}
puts("");
} int main()
{
int T_case = ;
while(~scanf("%d%d", &N, &M) && (N+M)){
for(int i = ; i < N; i++){
scanf("%lld", &A[i]);
}
for(int i = ; i < M; i++){
scanf("%lld", &B[i]);
}
if(N == ) x1 = A[], y = ;
else solve1();
if(M == ) x2 = B[], y2 = ;
else solve2(); printf("Case %d:\n", ++T_case);
//加法 if(y == || y2 == ){ //存在一个整数
if(y != && y2 == ){ //r2 为整数
ppt(x2*y+x1, y);
}
else if(y2 != && y == ){ //r1 为整数
ppt(x1*y2+x2, y2);
}
else{ //两个都是整数
printf("%lld\n", x1+x2);
}
}
else{ //两个都是分数
ppt(x1*y2+x2*y, y*y2);
} //减法 if(y == || y2 == ){ //存在一个整数
if(y != && y2 == ){ //r2 为整数
ppt(x1-x2*y, y);
}
else if(y2 != && y == ){ //r1 为整数
ppt(x1*y2-x2, y2);
}
else{ //两个都是整数
printf("%lld\n", x1-x2);
}
}
else{ //两个都是分数
ppt(x1*y2-x2*y, y*y2);
} //乘法 if(y == || y2 == ){ //存在一个整数
if(y != && y2 == ){ //r2 为整数
ppt(x2*x1, y);
}
else if(y2 != && y == ){ //r1 为整数
ppt(x1*x2, y2);
}
else{ //两个都是整数
printf("%lld\n", x1*x2);
}
}
else{ //两个都是分数
ppt(x1*x2, y*y2);
} //除法 if(y == || y2 == ){ //存在一个整数
if(y != && y2 == ){ //r2 为整数
ppt(x1, x2*y);
}
else if(y2 != && y == ){ //r1 为整数
ppt(x1*y2, x2);
}
else{ //两个都是整数
ppt(x1, x2);
}
}
else{ //两个都是分数
ppt(x1*y2, y*x2);
}
}
return ;
}