NiceMultiples | Topcoder Archive

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.

Definition

Class:: NiceMultiples
Method:: count
Parameters:: long, long, int
Returns:: int
Method signature:: int count(long M, long U, int B)
(be sure your method is public)

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.

Examples

```
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).

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.