The problem

Lets $$$f(x) = $$$ product of digits of $$$x$$$. Example: $$$f(123) = 1 * 2 * 3 = 6$$$, $$$f(990) = 9 * 9 * 0 = 0$$$, $$$f(1) = 1$$$

The statement is, given such limitation $$$N$$$, count the number of positive $$$x$$$ that $$$1 \leq x * f(x) \leq N$$$

Example: For $$$N = 20$$$, there are 5 valid numbers $$$1, 2, 3, 4, 11$$$

The limitation

• Subtask 1: $$$N \leq 10^6$$$
• Subtask 2: $$$N \leq 10^{10}$$$
• Subtask 3: $$$N \leq 10^{14}$$$
• Subtask 4: $$$N \leq 10^{18}$$$

My approach for subtask 1

• If $$$(x > N)$$$ or $$$(f(x) > N)$$$ then $$$(x * f(x) > N)$$$. So we will only care about $$$x \leq N$$$ that $$$x * f(x) \leq N$$$

ll cal(ll x, ll lim)
{
    ll res = x;
    do {
        int t = x % 10;
        if (res > lim / t) return -1; /// (x * f(x) > N)
        res *= t;
    } while (x /= 10);
    return res;
}

ll brute(ll n)
{
    ll res = 0;
    for (ll x = 1; x <= n; ++x)
        res += cal(x, n) > 0; /// 1 <= x * f(x) <= N

    return res;
}

My approach for subtask 2

• If $$$x$$$ contains $$$0$$$ then $$$f(x) = 0 \Rightarrow x * f(x) < 1$$$. We only care about such $$$x$$$ without $$$0$$$ digit

/// Run 2e13 under 1 secs in (-O2) flag
/// X: current X
/// Y: f(X)
/// T: X * f(X)

ll N;
int res = 0;
vector<int> d;
void build(ll X = 0, ll Y = 1, ll T = 0)
{
    if (T >= 1) ++res; /// 1 <= x * f(x) <= N
    for (int v = 1; v <= 9; ++v) /// if (v = 0) then f(x) = 0
    {
        ll NX = X * 10 + v; /// Insert rightmost digits
        ll NY = Y * v;      /// Calculate digits production
        ll NT = NX * NY;
        if (NT > N) break;  /// x * f(x) > N
        build(NX, NY, NT);
    }
}   

Here is the solution:

Let takes some $$$x$$$ satisfy $$$x * f(x) \leq N$$$

We can easily prove that $$$f(x) \leq x$$$, and because $$$x * f(x) \leq N$$$, we have $$$f(x) \leq \sqrt{N}$$$ (notice that $$$x$$$ might bigger than $$$\sqrt{N}$$$)

Since $$$f(x)$$$ is product of digits of $$$x$$$, which can be obtain by such digits {$$$1, 2, \dots, 9$$$}. So $$$f(x) = 2^a \times 3^b \times 5^c \times 7^d$$$

So we can bruteforces all possible tuple of such $$$(a, b, c, d)$$$ satisfy ($$$P = 2^a \times 3^b \times 5^c \times 7^d \leq \sqrt{N}$$$). There are about approximately $$$O(\sqrt[4]{N})$$$ such tuples (5914 tuples for $$$N = 10^{18}$$$