TheLuckyBasesDivOne
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. According to them, a lucky number is a number that contains only lucky digits in its decimal representation.
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 * 52 + 47, therefore representation of number 255 in the numeral system with base 52 consists of two digits, the leftmost digit is 4 and the rightmost digit is 47.
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 numbers (i.e. 4, 7, 44, 47, ...). For example, base 52 is lucky for the number 255.
You are given a
Constraints
- n will be between 1 and 10^16, inclusive.
255 Returns: 2
There are two lucky bases for the number 255: 52 and 62.
474 Returns: -1
All bases greater than 474 are lucky.
13 Returns: 0
No lucky bases here.
4748 Returns: 5
17 Returns: 0
Submissions are judged against all 86 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheLuckyBasesDivOne with a public method long long find(long long n) · 86 test cases · 2 s / 256 MB per case