TheLuckyBasesDivTwo
SRM 510 · 2010-11-01 · by Vasyl[alphacom]
Problem Statement
John and Brus believe that the digits 4 and 7 are lucky and all others are not.
Recently, they became interested in numeral systems with different bases. Normally, people use the numeral system with base 10 to represent numbers, however, there exist numeral systems with other bases. More exactly, for each integer B, B >= 2, there exists a numeral system with base B. In this system, there are B different digits, used to represent numbers from 0 to B-1, inclusive. In order to represent a positive integer A in such system, it's necessary to find such digits a[n], a[n-1], ..., a[0], that A = a[n] * B^n + a[n-1] * B^(n-1) + ... + a[0] * B^0 (here ^ denotes the power operator), and then write these digits from left to right, in this exact order. For example, 255 = 4 * 62 + 7, therefore representation of number 255 in the numeral system with base 62 consists of two digits, the leftmost digit is 4 and the rightmost digit is 7.
The base of numeral system B is called lucky for some integer number A if all digits of the number A represented in numeral system with base B are the lucky digits (i.e. 4 and 7). For example, base 62 is lucky for the number 255.
You are given a
Constraints
- n will be between 1 and 10^12, inclusive.
255 Returns: 1
The only lucky base for the number 255 is 62. Note that base 52 is not lucky. Representation of 255 in this base contains digits 4 and 47. The digit 47 is not lucky, even though its decimal representation contains only lucky digits. Only the digits 4 and 7 are considered to be lucky.
4 Returns: -1
All bases greater than 4 are lucky.
13 Returns: 0
No lucky bases here.
60 Returns: 2
17 Returns: 0
Submissions are judged against all 100 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheLuckyBasesDivTwo with a public method long long find(long long n) · 100 test cases · 2 s / 256 MB per case