Repeating Decimal or Expanding Fraction

Roby · Post by **Roby** » Mon Dec 05, 2005 5:47 am

Can someone explain to me how to find the repeating decimal or expanding fraction (202 and 275) from 2 integers? The algorithm only is OK. I've no idea with this problem. Thanx in advance

misof · Post by **misof** » Mon Dec 05, 2005 9:24 am

Implement division the way it's taught in primary school. Keep track of all the remainders you have seen so far. Once a remainder repeats, you are in a cycle.

Timo · Post by **Timo** » Mon Dec 05, 2005 9:37 am

Hi Roby,

I try to help you.

The number in decimal is repeated if when you divide them with the divisor they have same remainders appear twice.

I try explain you with sample input from problem 275.

input :
3 7

output :
.428571
The last 6 digits repeat forever.

output '.'

N

1. multiply 3 by 10
30 / 7 = 4 , output 4
30 % 7 = 2 (remember this value)

2. multiply 2 by 10
20 / 7 = 2, output 2
20 % 7 = 6 (remember this value)

3. multiply 6 by 10
60 / 7 = 8, output 8
60 % 7 = 4 (remember this value)

4. multiply 4 by 10
40 / 7 = 5, output 5
40 % 7 = 5 (remember this value)

5. multiply 5 by 10
50 / 7 = 7, output 7
50 % 7 = 1 (remember this value)

6. multiply 1 by 10
10 / 7 = 1, output 1
10 % 7 = 3 (remember this value)

7. multiply 3 by 10
30 / 7 = 4, output 4
30 % 7 = 2 (2 is appear twice)

to know how many digits repeat just output when :
(second time appear) - (first time appear)

in the example above first time '2' appear when N=1;
second time '2' appear when N=7;

so output 7-1 = 6.
6 digits repeat forever.

I hope you understand what I mean and can get AC.
Sorry for my poor English.

Roby · Post by **Roby** » Tue Dec 06, 2005 11:02 am

thanx for the reply, I'll try it.

hehehe, forgot all that basics...