If ~X~ is larger than say ~10^5~, then ~B/X~ is at most ~10^6~, meaning that there are at most one million multiples of ~X~ to check. A "naive" solution that checks each and verifies that it is composed of the given digits is efficient enough.

If ~X~ is at most ~10^5~, then integers divided by ~X~ give remainders no larger than ~10^5-1~.

We will construct the function ~f(n, prefix)~, the number of multiples of ~X~ between ~A~ and ~B~, if we still have to place ~n~ more digits (of ~11~) and ~prefix~ represents the digits already placed.

To calculate the values of this function, first observe that, for any ~n~ and ~prefix~, we can only form numbers between ~prefix \cdot 10^n~ and ~prefix \cdot 10^{n+1}-1~, inclusive. Based on this we recognise three cases:

• If all numbers are between ~A~ and ~B~, then the actual prefix doesn't matter when forming the rest of the number, just its remainder when divided by ~X~. The limited range of the remainders reduces the state space and we can memoize the values of the function based on the remainder.
• If all numbers are less than ~A~ or greater than ~B~, then the value is zero.
• If some (but not all) numbers are between ~A~ and ~B~, then the value of the function doesn't depend only on the remainder of dividing the prefix by ~X~, so it isn't possible to memoize the value of the function on the remainder. Luckily, there are few such cases (proportional to the length of the number).