NiceMultiples
SRM 765 · 2019-08-22 · by misof
Problem Statement
Consider all multiples of a positive integer M that do not exceed U. If we write each of them in base B, how many of them don't contain any zeros? Return the answer modulo 10^9 + 7.
Constraints
- M will be between 1 and 10^12, inclusive.
- U will be between M and 10^12, inclusive.
- B will be between 2 and 16, inclusive.
1 100 2 Returns: 6
The multiples of 1 that do not contain any zeros in base 2 are the numbers 1, 3, 7, 15, 31, and 63. (In base 2, these are 1, 11, 111, 1111, 11111, and 111111.)
6 123456789 3 Returns: 0
In base 3, each multiple of 6 ends in a zero.
2 117 10 Returns: 43
3333333333 9999999999 10 Returns: 3
Watch out for integer overflow.
1 100000000000 10 Returns: 303691814
The answer is (9 + 9^2 + ... + 9^11) modulo (10^9 + 7).
Submissions are judged against all 170 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NiceMultiples with a public method int count(long long M, long long U, int B) · 170 test cases · 2 s / 256 MB per case