FractionInDifferentBases | Topcoder Archive

Problem Statement

This problem statement contains superscripts and/or subscripts. It may not display properly outside the applet.

It is well-known that when writing a fraction as a rational number, we will either get a finite expansion or an infinite (but periodic) expansion. For example, 1/8 written in base 10 is 0.125, and 1/9 written in base 10 is 0.1111...

The same fraction can have a finite expansion in some bases and an infinite one in other bases. For example, 1/9 had an infinite expansion in base 10, but 1/9 written in base 3 is 0.01 and 1/9 in base 9 is 0.1.

Little Arthur loves numbers and especially the ones that are infinitely long. For a given fraction P/Q he would like to find all integer bases between A and B, inclusive, such that the fraction has an infinite expansion.

Given ints P, Q, A, and B return the number of such bases.

Definition

Class:: FractionInDifferentBases
Method:: getNumberOfGoodBases
Parameters:: long, long, long, long
Returns:: long
Method signature:: long getNumberOfGoodBases(long P, long Q, long A, long B)
(be sure your method is public)

Notes

Number X written in an integer base b is a sequence of digits (containing a single separator point, if the number is not an integer) dndn-1..d1d0.d-1..d-m where each di has an integer value between 0 and b-1, inclusive.
The notation effectively means that X = dn*bn + dn-1*bn-1 + .. + d1*b1 + d0*b0 + d-1*b-1 + .. + d-m*b-m.
Note that X having an infinite expansion in base b means that number X cannot be expressed as a sum with finitely many powers of b.

Constraints

P will be between 0 and 1000000000000 (1012), inclusive.
Q will be between 1 and 1000000000000 (1012), inclusive.
A and B will each be between 2 and 1000000000000000000 (1018), inclusive.
A will be less than or equal to B.

Examples

```
1
```
```
2
```
```
10
```
```
10
```
```
Returns: 0
```
1/2 in base 10 is 0.5, thus, there is no base in the interval where 1/2 has an infinite expansion.
```
1
```
```
9
```
```
9
```
```
10
```
```
Returns: 1
```
From the problem statement we see that 1/9 has an infinite expansion in base 10, but not in base 9.
```
5
```
```
6
```
```
2
```
```
10
```
```
Returns: 8
```
```
2662
```
```
540
```
```
2
```
```
662
```
```
Returns: 639
```

Returns: 2010495

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.