Problem Statement
For a positive integer x, we say that the base b >= 2 is light if the integer x written in base b has digit sum at most 2.
For example:
- Base b=10 is light for x=1000, x=10010 and also for x=200.
- Base b=2 is light for x=65 because 65 written in base-2 is "1000001", and the digit sum of that is 2.
- Base b=47 is light for x = 4418 = 2*47*47.
For each of the numbers A, A+S, A+2*S, ..., A+(N-1)*S, determine their smallest light base. Return the sum of those bases, modulo (10^9 + 7).
Definition
- Class:
- Based
- Method:
- solve
- Parameters:
- long, long, int
- Returns:
- int
- Method signature:
- int solve(long A, long S, int N)
- (be sure your method is public)
Notes
- Each positive integer has at least one light base, so the return value is always well-defined.
Constraints
- N will be between 1 and 100,000, inclusive.
- A will be positive.
- S will be positive.
- All N numbers of the form A + i*S will be between 1 and 10^18, inclusive.
Examples
30
2
5
Returns: 28
We are interested in the numbers 30, 32, 34, 36, and 38. For the numbers 32, 34, and 36 the smallest light base is b=2. (They are "100000", "100010", and "100100" in base-2.) The smallest light base for x=30 is b=3 ("1010"), and the smallest light base for x=38 is b=19 ("20"). The return value is (3+2+2+2+19) mod (10^9 + 7).1
4417
2
Returns: 49
The smallest valid base is b=2. This is a light base for x=1, as 1 in base 2 is "1". As mentioned in the statement, b=47 is a light base for x=4418. It turns out to be the smallest light base for this x.987654321987654321
12347
2
Returns: 611117350
The return value is (987654321987654320 + 493827160993833334) mod (10^9 + 7).