The first observation we can make is that, for all positive integers ~x~, the digit-product ~p(x)~ is always less than or equal to ~x~. From ~x \times p(x) \le B \le 10^{18}~ we can deduce that ~p(x) \le B \le 10^9~.

Because ~p(x)~ is a product of digits, its prime factors can only be ~2~, ~3~, ~5~ and ~7~. The number of different integers with only ~2~, ~3~, ~5~ and ~7~ in their prime factorization that are less than or equal to ~10^9~ is quite small (exactly ~5194~).

Since there are relatively few such values, we can iterate through all of them. Now, it suffices to solve the following problem for each fixed product ~P~:

Let ~P = p(x) = 2^a 3^b 5^c 7^d~. How many numbers between ~\lceil \frac A P \rceil~ and ~\lfloor \frac B P \rfloor~ have product of digits equal to ~P~?

We can count all such numbers by considering them digit by digit from left to right using a recursive algorithm.

Let rec( string prefix, int N, int prod ) be such a recursive algorithm. The algorithm returns the total number of integers that start with prefix and have ~N~ more digits whose product is prod. Its arguments are:

• prefix is the part of the number generated so far
• N is the number of digits that still needs to be generated and
• prod is the target digit-product of the yet to be generated part of the number.

rec( string prefix, int N, int prod )
    Let max be a number we get when we append prefix with N nine digits
    Let min be a number we get when we append prefix with N zero digits

    If max < ceil(A/P) or min > floor(B/P) then Return 0
    If N = 0 then
        If prod = 1 then Return 1
        else Return 0

    Count = 0
    For each digit D from 1 to 9
        If D divides prod then
            Count = Count+rec( prefix appended by digit D, N-1, prod/D )
    Return Count

To speed things up, we will add memoization to the algorithm described above. In order to memorize the return values of the function efficiently, we consider two cases:

• If ~min \ge \lceil \frac A P \rceil~ and ~max \le \lfloor \frac B P \rfloor~ hold (i.e. all possible values that can be generated from this moment on are within the bounds), then the result is the same no matter the value of the number we generated so far. Therefore, we can ignore the prefix parameter.

  We are left with only N and prod as state parameters, and since N can take on only ~18~ different values and prod only ~5194~ different values, we can store the result in a table and use it whenever we encounter the same parameters again.

• If one of the statements ~min \ge \lceil \frac A P \rceil~ and ~max \le \lfloor \frac B P \rfloor~ is false then the string prefix is either a prefix of ~\lceil \frac A P \rceil~ or a prefix of ~\lfloor \frac B P \rfloor~, and the number of additional states we have to memorize is linear in ~N~ (the number of digits).

Total time complexity of the algorithm is ~\mathcal O(K(\sqrt B) \log_{10} B)~ where ~K(x)~ is the number of different integers with only ~2~, ~3~, ~5~ and ~7~ in their prime factorization that are less than or equal to ~x~. For ~B = 10^{18}~, we have ~K(\sqrt B) = 5194~ and ~\log_{10} B = 18~.