Counting such number whose digit product multiple to itself smaller than given number

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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$$$

Calculating x * f(x) - O(log10(x))

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;
}

Counting - O(n log10(n))

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 \times f(x) < 1$$$. We only care about such $$$x$$$ without $$$0$$$ digit

Building function - O(result + log10(n))

/// 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 $$$1 \leq 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 (493 tuples for $$$N = 10^9$$$ and 5914 tuples for $$$N = 10^{18}$$$)

Find all possible tuples - O(quartic_root(N))

/// [L, R] = [1, N]
/// lim = sqrt(N)
ll solve(int p2 = 0, int p3 = 0, int p5 = 0, int p7 = 0, ll P = 1)
{
    if (P > lim) return 0; /// Dont care such tuples whose P > sqrt(N)

    VL = (L + val - 1) / val; ///  ceil(L / P)
    VR = R / val;             /// floor(R / P)
    ll res = magic(0, 18, p2, p3, p5, p7); /// Calculating subproblem

    /// By doing these if-condition, it is guarantee that all tuples generated are all unique
    if (!p3 && !p5 && !p7) res += solve(p2 + 1, p3, p5, p7, P * 2); /// Continue increasing a
    if (       !p5 && !p7) res += solve(p2, p3 + 1, p5, p7, P * 3); /// Continue increasing b
    if (              !p7) res += solve(p2, p3, p5 + 1, p7, P * 5); /// Continue increasing c
                           res += solve(p2, p3, p5, p7 + 1, P * 7); /// Continue increasing d

    return res;
}

For each tuples, we need to counting the numbers of such $$$x$$$ that $$$1 \leq x \times f(x) \leq N$$$ and $$$f(x) = P$$$.

We have the value $$$P$$$, so $$$\lceil \frac{1}{P} \rceil \leq x \leq \lfloor \frac{N}{P} \rfloor$$$.
We have the value $$$f(x) = P$$$, so $$$x$$$ can be made by digits having the product exactly $$$P$$$, so we can do some DP-digit

So now we have to solve this DP-digit problem: Calculate numbers of such $$$x$$$ ($$$L \leq x \leq R$$$) whose $$$f(x) = P$$$

Solving Subproblem

We try to build each digits by digits for $$$X$$$. Because $$$X \leq N$$$, so we have to build about $$$18$$$ digits.

Lets make a recursive function $$$magic(X, N, p2, p3, p5, p7)$$$

Lets make some definition

Notice that

Ugly precalculation code - O(1)

const int l2 = 30, l3 = 18, l5 = 12, l7 = 10, l10 = 19;
int       pw2[l2], pw3[l3], pw5[l5], pw7[l7]; ll pw10[l10];
int       cost[10][10];
void precal()
{
    pw2[0] = pw3[0] = pw5[0] = pw7[0] = pw10[0] = 1; 
    for (int i2 = 1; i2 < l2; ++i2) pw2[i2] = pw2[i2 - 1] * 2;
    for (int i3 = 1; i3 < l3; ++i3) pw3[i3] = pw3[i3 - 1] * 3;
    for (int i5 = 1; i5 < l5; ++i5) pw5[i5] = pw5[i5 - 1] * 5;
    for (int i7 = 1; i7 < l7; ++i7) pw7[i7] = pw7[i7 - 1] * 7;
    for (int i  = 1; i  <l10; ++i ) pw10[i] = pw10[i - 1] * 10;                            
                                                                                 /// 2357
    cost[1][2] = 0;     cost[1][3] = 0;     cost[1][5] = 0;     cost[1][7] = 0; /// 0000 1
    cost[2][2] = 1;     cost[2][3] = 0;     cost[2][5] = 0;     cost[2][7] = 0; /// 1000 2
    cost[3][2] = 0;     cost[3][3] = 1;     cost[3][5] = 0;     cost[3][7] = 0; /// 0100 3
    cost[4][2] = 2;     cost[4][3] = 0;     cost[4][5] = 0;     cost[4][7] = 0; /// 2000 4
    cost[5][2] = 0;     cost[5][3] = 0;     cost[5][5] = 1;     cost[5][7] = 0; /// 0010 5
    cost[6][2] = 1;     cost[6][3] = 1;     cost[6][5] = 0;     cost[6][7] = 0; /// 1100 6
    cost[7][2] = 0;     cost[7][3] = 0;     cost[7][5] = 0;     cost[7][7] = 1; /// 0001 7
    cost[8][2] = 3;     cost[8][3] = 0;     cost[8][5] = 0;     cost[8][7] = 0; /// 3000 8
    cost[9][2] = 0;     cost[9][3] = 2;     cost[9][5] = 0;     cost[9][7] = 0; /// 0200 9
}

magic function - O(18*p2*p3*p5*p7)

ll VL, VR;
ll f[l10][l2][l3][l5][l7];
ll magic(ll X, int N, int p2, int p3, int p5, int p7)
{
    if (p2 < 0 || p3 < 0 || p5 < 0 || p7 < 0) return 0;
    if (N == 0) return (p2 + p3 + p5 + p7 == 0) && (VL <= X && X <= VR);

    ll mn = X * pw10[N];
    ll mx = mn + pw10[N] - 1;
    if (mx < VL || mn > VR) return 0;

    ll &save = f[N][p2][p3][p5][p7];
    bool memo = (VL <= mn) && (mx <= VR);
    if (memo) if (save != -1) return save;
    
    ll res = 0;
    if (X == 0) res = magic(0, N - 1, p2, p3, p5, p7);
    for (int v = 1; v <= 9; ++v)
    {
        int c2 = cost[v][2];
        int c3 = cost[v][3];
        int c5 = cost[v][5];
        int c7 = cost[v][7];
        res += magic(X * 10 + v, N - 1, p2 - c2, p3 - c3, p5 - c5, p7 - c7);
    }
    if (memo) save = res;
    
    return res;
}

About the proving stuff

1) $$$\forall x \in \mathbb{N}, f(x) \leq x$$$

Proof: $$$x = \overline{\dots dcba} = \dots + d \times 10^3 + c \times 10^2 + b \times 10^1 + a \times 10^0 \geq \dots \times d \times c \times b \times a = f(x)$$$

2) If $$$x$$$ satisfy then $$$f(x) \leq \sqrt{R}$$$ must be satisfied

Proof: $$$x \times f(x) \leq R \Rightarrow f(x) \times f(x) \leq R \Rightarrow f(x) \leq \sqrt{R}$$$

3) $$$\exists\ a, b, c, d \in \mathbb{N} \rightarrow f(x) = 2^a \times 3^b \times 5^c \times 7^d$$$

Since $$$x = \overline{\dots dcba} \Rightarrow (0 \leq \dots, d, c, b, a \leq 9)$$$ and $$$f(x) = \dots \times d \times c \times b \times a$$$
And we also have $$$\forall$$$ digit $$$v$$$ ($$$v \in \mathbb{N}, 0 \leq v \leq 9$$$) $$$\rightarrow \exists\ a, b, c, d \in \mathbb{N} \rightarrow v = 2^a \times 3^b \times 5^c \times 7^d$$$
And because $$$f(x)$$$ is the product of digits of $$$x$$$, hence the statement is correct

4) If we know $$$f(x)$$$ we can find such $$$x$$$ satisfy $$$x \in [L, R]$$$

Proof: Since $$$f(x)$$$ is created from factors of digits of $$$x$$$, so $$$x$$$ can also be generated using the factors

5) Number of tuples $$$(a, b, c, d)$$$ satisfy $$$P = 2^a \times 3^b \times 5^c \times 7^d \leq \sqrt{R}$$$ is very small

Lets $$$O(k(x)) = O(log_2(x) \times log_3(x) \times log_5(x) \times log_7(x))$$$
Since each value $$$x$$$ have the upper bound of $$$log_x(\sqrt{R})$$$. So the complexity is about $$$O(log_2(\sqrt{R}) \times log_3(\sqrt{R}) \times log_5(\sqrt{R}) \times log_7(\sqrt{R})) = O(k(\sqrt{R})) \leq O(log_2(\sqrt{R})^4)$$$
But actually for $$$R \leq 10^{18}$$$, the complexity is just about $$$O(k(\sqrt[4]{R}))$$$

Weak proof - N = 10^k

With (N = 1) -> Found 1 valid tuples || upper_bound 1
With (N = 10) -> Found 3 valid tuples || upper_bound 4
With (N = 100) -> Found 10 valid tuples || upper_bound 10
With (N = 1000) -> Found 22 valid tuples || upper_bound 24
With (N = 10000) -> Found 46 valid tuples || upper_bound 51
With (N = 100000) -> Found 83 valid tuples || upper_bound 96
With (N = 1000000) -> Found 141 valid tuples || upper_bound 166
With (N = 10000000) -> Found 225 valid tuples || upper_bound 269
With (N = 100000000) -> Found 338 valid tuples || upper_bound 415
With (N = 1000000000) -> Found 493 valid tuples || upper_bound 613
With (N = 10000000000) -> Found 694 valid tuples || upper_bound 875
With (N = 100000000000) -> Found 951 valid tuples || upper_bound 1213
With (N = 1000000000000) -> Found 1273 valid tuples || upper_bound 1641
With (N = 10000000000000) -> Found 1670 valid tuples || upper_bound 2173
With (N = 100000000000000) -> Found 2155 valid tuples || upper_bound 2825
With (N = 1000000000000000) -> Found 2736 valid tuples || upper_bound 3614
With (N = 10000000000000000) -> Found 3427 valid tuples || upper_bound 4558
With (N = 100000000000000000) -> Found 4246 valid tuples || upper_bound 5676
Error: 5710

Weak proof - N = 2^k

With (N = 1) -> Found 1 valid tuples || upper_bound 1
With (N = 10) -> Found 3 valid tuples || upper_bound 4
With (N = 100) -> Found 10 valid tuples || upper_bound 10
With (N = 1000) -> Found 22 valid tuples || upper_bound 24
With (N = 10000) -> Found 46 valid tuples || upper_bound 51
With (N = 100000) -> Found 83 valid tuples || upper_bound 96
With (N = 1000000) -> Found 141 valid tuples || upper_bound 166
With (N = 10000000) -> Found 225 valid tuples || upper_bound 269
With (N = 100000000) -> Found 338 valid tuples || upper_bound 415
With (N = 1000000000) -> Found 493 valid tuples || upper_bound 613
With (N = 10000000000) -> Found 694 valid tuples || upper_bound 875
With (N = 100000000000) -> Found 951 valid tuples || upper_bound 1213
With (N = 1000000000000) -> Found 1273 valid tuples || upper_bound 1641
With (N = 10000000000000) -> Found 1670 valid tuples || upper_bound 2173
With (N = 100000000000000) -> Found 2155 valid tuples || upper_bound 2825
With (N = 1000000000000000) -> Found 2736 valid tuples || upper_bound 3614
With (N = 10000000000000000) -> Found 3427 valid tuples || upper_bound 4558
With (N = 100000000000000000) -> Found 4246 valid tuples || upper_bound 5676
Error: 5710

Code

#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

typedef long long ll;

ll L;
ll R;
int lim;
ll solve(int p2 = 0, int p3 = 0, int p5 = 0, int p7 = 0, ll val = 1)
{
    if (val > lim) return 0;

    ll res = 1;
    if (!p3 && !p5 && !p7) res += solve(p2 + 1, p3, p5, p7, val * 2);
    if (       !p5 && !p7) res += solve(p2, p3 + 1, p5, p7, val * 3);
    if (              !p7) res += solve(p2, p3, p5 + 1, p7, val * 5);
                           res += solve(p2, p3, p5, p7 + 1, val * 7);

    return res;
}

int main()
{
    freopen("Test.OUT", "w", stdout);

    double error = 0;
    ll mul = 10;
    ll over = 1e19 / mul;
    for (ll t = 1; t < over; t *= mul)
    {
        L = 1;
        R = t;
        lim = sqrt(R);
        double base = log(sqrt(sqrt(R))) + 1;
        int complexity = ceil(0.5 + (base / log(2)) * (base / log(3)) * (base / log(5)) * (base / log(7)));
        cout << "With (N = " << R << ") -> Found " << solve() << " valid tuples || upper_bound " << complexity << endl;
        error += abs(expected - solve());
    }
    cout << "Error: " << error;

    return 0;
}

About the complexity:

$$$O(h(x)) = O(log_{10}(R))$$$ is number of digits we have to build
$$$O(k(x)) = O(log_2(R) \times log_3(R) \times log_5(R) \times log_7(R)) \approx O(log_2(R)^4)$$$ is product of all prime digits $$$p$$$ with its maximum power $$$k$$$ satisfy $$$p^k \leq N$$$
$$$O(g(x)) = O(k(\sqrt{R}))$$$ is number of such valid tuples, but for $$$1 \leq N \leq 10^{18}$$$ it is about $$$\approx O(k(\sqrt[4]{R})) \leq O(log_2^4{\sqrt[4]{R}})$$$
The space complexity is $$$O(SPACE) = O(h(x) \times k(x)) \approx O(log(R)^5)$$$
The time complexity is $$$O(TIME) = O(SPACE) + O(g(x) \times k(x)) \approx O(log(R)^4 \times log_2^4{\sqrt[4]{R}})$$$

Rev.	Кто	Когда	Δ	Комментарий
en21	SPyofgame	2020-11-08 18:08:04	60
en20	SPyofgame	2020-11-07 11:02:44	132	Tiny change: '\leq N$ ? \n> Since my ' -> '\leq N$ ? Since my '
en19	SPyofgame	2020-11-07 10:59:37	1409	Tiny change: '4, 11$\n\n-------\n\n#### T' -> '4, 11$\n\n========\n\n#### T'
en18	SPyofgame	2020-11-06 06:29:46	3554	(published)
en17	SPyofgame	2020-11-06 06:02:44	2761	Tiny change: 'sqrt{R})^4 \times log_2(R)^4)$\n\n-' -> 'sqrt{R})^4)$\n\n-' (saved to drafts)
en16	SPyofgame	2020-11-05 18:40:17	1012
en15	SPyofgame	2020-11-05 18:39:30	3010	Tiny change: 'leq x$\n\n> $x = \ove' -> 'leq x$\n\n Proof: $x = \ove'
en14	SPyofgame	2020-11-05 18:11:26	3	Tiny change: '$p^k \leq MAXN$, which ' -> '$p^k \leq N$, which '
en13	SPyofgame	2020-11-05 17:56:06	40
en12	SPyofgame	2020-11-05 17:53:26	43
en11	SPyofgame	2020-11-05 17:42:05	84
en10	SPyofgame	2020-11-05 16:44:33	16	Tiny change: ' summary="Function f(x) - O(' -> ' summary="Calculating x * f(x) - O('
en9	SPyofgame	2020-11-05 15:53:37	88	Tiny change: 'uch those numbers\n- $pw10[' -> 'uch those variables we use\n- $pw10['
en8	SPyofgame	2020-11-05 15:52:01	107
en7	SPyofgame	2020-11-05 15:51:08	61
en6	SPyofgame	2020-11-05 15:50:12	6163	Tiny change: ' build yet)\n\n> Wher' -> ' build yet\n\n> Wher' (published)
en5	SPyofgame	2020-11-05 15:05:42	552	Tiny change: 'y $O(\sqrt{\sqrt{N}}' -> 'y $O(\sqrt[4]{\sqrt{N}}' (saved to drafts)
en4	SPyofgame	2020-11-05 05:03:48	23
en3	SPyofgame	2020-11-05 05:03:05	12
en2	SPyofgame	2020-11-05 05:02:48	170	Tiny change: 'unction - O(result)' -> 'unction - approx O(result)' (published)
en1	SPyofgame	2020-11-05 04:54:10	1886	Initial revision (saved to drafts)