Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Period of an Infinite Binary Expansion
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 4381Accepted: 1290


Let {x} = 0.a1a2a3... be the binary representation of the fractional part of a rational number z. Suppose that {x} is periodic then, we can write

{x} =

for some integers r and s with r ≥ 0 and s > 0. Also, ( a nonterminating and repeating binary subsequence of {x}.

The subsequence x1 = a1a2 ... aris called the preperiod of {x} and x2 = ar+1ar+2 ... ar+s is the period of {x}.

Suppose that |x1| and |x2| are chosen as small as possible then x1 is called the least preperiod and x2 is called the least period of {x}.

For example, x = 1/10 = 0.0001100110011(00110011)w and 0001100110011 is a preperiod and 00110011 is a period of 1/10.

However, we can write 1/10 also as 1/10 = 0.0(0011)w and 0 is the least preperiod and 0011 is the least period of 1/10.

The least period of 1/10 starts at the 2nd bit to the right of the binary point and the the length of the least period is 4.

Write a program that finds the position of the first bit of the least period and the length of the least period where the preperiod is also the minimum of a positive rational number less than 1.


Each line is test case. It represents a rational number p/q where p and q are integers, p ≥ 0 and q > 0.


Each line corresponds to a single test case. It represents a pair where the first number is the position of the first bit of the least period and the the second number is the length of the least period of the rational number.

Sample Input


Sample Output

Case #1: 2,4 
Case #2: 1,4 
Case #3: 4,4 
Case #4: 7,11


[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator