Official Analysis (C++)

Explanation

First, to reduce our problem, we observe the following:

1. Being divisible by $M$ means that our number is equivalent to $0$, mod $M$.
2. Let $\texttt{count\_magic}(x)$ define all the magic numbers $\leq x$. The frequency of magic numbers in the range $[a, b]$ is $\texttt{count\_magic}(b) - \texttt{count\_magic}(a - 1)$.

Then, we can use a somewhat typical DP state to model the problem.

Let $\texttt{dp}[i][j][k]$ represent all the possibilities, when:

• We have considered the first $i$ digits
• Our number is equivalent to $j$, mod $M$
• $k$ represents if our number is "free" or not

  • If the first $i$ digits in our number match up with the bound or not

Then, after considering all of our digits, we consider all the numbers equivalent to $0$ mod $M$.

Here are some key points to consider when implementing the problem:

• Handling $a-1$ in string form is annoying. Instead, we can consider the values of $\texttt{count\_magic}(a)$ and $\texttt{count\_magic}(b)$, then manually handle $a$ on its own.
• Note how the problem guarantees that $a$ and $b$ are the same length. This means that we can effectively ignore leading zeroes in our implementation.

Implementation

Time Complexity: $\mathcal{O}(M \cdot D)$, where $D$ is the number of digits in $a$ and $b$.

Copy
#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1e9 + 7;

int count_magic(int m, int d, string bound, bool ok) {
	if (bound.length() == 1) {
		int num_good = 0;
		int cur_digit = bound[0] - '0';
		for (int i = 0; i < cur_digit; i++) { num_good += (i != d) && (i % m == 0); }