FractionInDifferentBases
SRM 540 · 2011-11-22 · by nV
SRM 540 · 2011-11-22 · by nV · Math
Problem Statement
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
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
0)
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)
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.
2)
5 6 2 10 Returns: 8
3)
2662 540 2 662 Returns: 639
4)
650720 7032600 2012 2012540 Returns: 2010495
Submissions are judged against all 96 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FractionInDifferentBases with a public method long long getNumberOfGoodBases(long long P, long long Q, long long A, long long B) · 96 test cases · 2 s / 256 MB per case