Based
SRM 851 · 2023-12-06 · by misof
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).
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.
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 100000 Returns: 190937008
987654321987654321 12347 2 Returns: 611117350
The return value is (987654321987654320 + 493827160993833334) mod (10^9 + 7).
1099511627776 1099511627776 99945 Returns: 124571092
Submissions are judged against all 150 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Based with a public method int solve(long long A, long long S, int N) · 150 test cases · 2 s / 256 MB per case