CSUOJ 1638 Continued Fraction

1638: Continued Fraction

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

Input

Output

Sample Input

4 3
5 1 1 2
5 2 2

Sample Output

11
0 5
30 4 6
1 27

HINT

Source

解题:主要任务是把任一一个分数化成连分式。

方法就是分子分母同时不断的除以分子,直到分子为0。

至于加,减,乘,除都是先算出分数,然后把分数化成连分数。。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 int n,m,a1[20],a2[20];
 5 LL gcd(LL x,LL y){
 6     return y?gcd(y,x%y):x;
 7 }
 8 void dfs(LL &A,LL &B,int *arr,int cur,int dep){
 9     if(cur == dep-1){
10         A = arr[cur];
11         B = 1;
12     }
13     if(cur >= dep-1) return;
14     LL tmpA,tmpB;
15     dfs(tmpA,tmpB,arr,cur+1,dep);
16     LL theGCD = gcd(A = arr[cur]*tmpA + tmpB,B = tmpA);
17     A /= theGCD;
18     B /= theGCD;
19 }
20 void print(LL x,LL y){
21     LL GCD = gcd(x,y);
22     LL tmp = (x /= GCD)/(y /= GCD),p = x - tmp*y;
23     printf("%lld%c",tmp,p?‘ ‘:‘\n‘);
24     if(p) print(y,p);
25 }
26 int main(){
27     while(~scanf("%d %d",&n,&m)){
28         for(int i = 0; i < n; ++i) scanf("%d",a1+i);
29         for(int i = 0; i < m; ++i) scanf("%d",a2+i);
30         LL A1 = 0,B1 = 1,A2 = 0,B2 = 1;
31         dfs(B1,A1,a1,1,n);
32         dfs(B2,A2,a2,1,m);
33         A1 += a1[0]*B1;
34         A2 += a2[0]*B2;
35         print(A1*B2 + A2*B1,B1*B2);
36         print(A1*B2 - A2*B1,B1*B2);
37         print(A1*A2,B1*B2);
38         print(A1*B2,A2*B1);
39     }
40     return 0;
41 }

时间: 06-02

CSUOJ 1638 Continued Fraction的相关文章

HDU - 3556 - Continued Fraction

先上题目: Continued Fraction Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)Total Submission(s): 332    Accepted Submission(s): 106 Problem Description Dumbear loves numbers very much.One day Dumbear found that each n

Continued Fractions CodeForces - 305B (java+高精 / 数学)

A continued fraction of height n is a fraction of form . You are given two rational numbers, one is represented as  and the other one is represented as a finite fraction of height n. Check if they are equal. Input The first line contains two space-se

欧拉工程第65题:Convergents of e

题目链接 现在做这个题目真是千万只草泥马在心中路过 这个与上面一题差不多 这个题目是求e的第100个分数表达式中分子的各位数之和 What is most surprising is that the important mathematical constant,e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...]. The first ten terms in the sequence of convergents for e are: 2, 3,

欧拉计划(python) problem 65

Convergents of e Problem 65 The square root of 2 can be written as an infinite continued fraction. √2 = 1 + 1   2 + 1     2 + 1       2 + 1         2 + ... The infinite continued fraction can be written, √2 = [1;(2)], (2) indicates that 2 repeats ad

欧拉计划(python) problem 64

Odd period square roots Problem 64 All square roots are periodic when written as continued fractions and can be written in the form: √N = a0 + 1   a1 + 1     a2 + 1       a3 + ... For example, let us consider √23: √23 = 4 + √23 - 4 = 4 +  1  = 4 +  1

C++开源库集合

| Main | Site Index | Download | mimetic A free/GPL C++ MIME Library mimetic is a free/GPL Email library (MIME) written in C++ designed to be easy to use and integrate but yet fast and efficient. It is based on the C++ standard library and heavily us

Infinite Expressions for Pi

John Wallis (1655) took what can now be expressed as and without using the binomial theorem or integration (not invented yet) painstakingly came up with a formula for  to be  . William Brouncker (ca. 1660's) rewrote Wallis' formula as a continued fra

湖南多校对抗5.24

据说A,B,C题都比较水这里就不放代码了 D:Facility Locations 然而D题是一个脑经急转弯的题:有m行,n列,每个位置有可能为0,也可能不为0,问最多选K行是不是可以使得每一列都至少有一个0,其中代价c有个约束条件:These costs satisfy a locality property: for two clients j and j’ and two facilities i and i’, we have cij ≤ ci’j + ci’j’ + cij’ . 一看

cf 305B

F - Continued Fractions Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u Submit Status Practice CodeForces 305B Appoint description:  System Crawler  (2015-01-10) Description A continued fraction of height n is a fraction