MATHS - Mathematics

no tags 

One could define mathematics as the study of quantity, structure, space and change and as the science of infinity. Sometimes very abstract, mathematics finds nevertheless applications in many engineering domains. The figure below shows so-called Ford circles. These circles are disjoint or tangent and fill the space in a very compact way! Starting with large circles, the space between these circles can be filled with circles of smaller diameter, and so on and so forth.



Mathematicians observed that the diameters and positions of the centers of these circles follow a given scheme, which can be described with the help of Farey sequences. The Farey sequence of order N is the sequence of completely reduced fractions between 0 and 1, which have denominators less than or equal to N, arranged in increasing size. Thus each Farey sequence starts with the value 0, denoted by the fraction 01, and ends with the value 1, denoted by the fraction 11.

The Amazing Circle Mathematicians (ACM) are interested in the number of terms contained in such a Farey sequence as well as in certain precise terms, which they name Interesting and Curious Position In Circle (ICPC). Your job is to provide the ACMs with this abstract information, which helps them to better understand the Ford circles.



The input consists of several test-cases, one per line. Each test-case consists of two numbers, the first is the order N (2<=N<=106) of the Farey sequence the ACM is interested in and the second is the ICPC P (1<=P<=104) . Input terminates on a line containing 0 0 which must not be processed.



For each test-case, output first the ICPC, then the total number of terms in the given Farey sequence.



2 2

6 12

14 35

0 0



1/2 3

5/6 13

6/11 65


hide comments
Abhishek: 2014-12-29 17:54:02

@Francky will an O(n) solution pass ? , i am getting TLE
Do i necessarly use direct formula for the length of seq ?

--ans(Francky)--> I think most the AC have complexity of O(N×ln(N)) + O(T×K), where T is number of test case (small), so only the first part really count. Mine is different, and it can be much faster, I did half brute-force.

Last edit: 2014-12-29 18:06:47
Francky: 2014-12-29 13:42:38

Number of test case is small : between 200 and 500. I didn't use my fastest code. If you want to take #1, you should take a look at my next problem : ETFS. coming soon.
edit : done.
edit2 : There will be another HARD variant : PERIOD1 ; coming soon. (last edit : done)

Last edit: 2014-12-29 22:37:41

Added by:Christian Kauth
Time limit:3.295s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64