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 small amount of 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 - $$$VL, VR$$$ means the range of $$$x$$$ needed to get $$$1 \leq x \times f(x) \leq N$$$
- Current prefix of building number is $$$X$$$
- We $$$N$$$ digits left to build to the right of $$$X$$$
- $$$p2, p3, p5, p7$$$ means the left factors in $$$f(x)$$$
- $$$min(X, N) = X \times 10^N = \overline{X\underbrace{00000\dots}_{N}}$$$ means the smallest possible number with prefix $$$X$$$ and $$$N$$$ left digits
- $$$max(X, N) = X \times 10^N + 10^N - 1 = \overline{X\underbrace{99999\dots}_{N}}$$$ means the greatest possible number with prefix $$$X$$$ and $$$N$$$ left digits
- $$$cost[v][p]$$$ means greatest divisor $$$p^k$$$ in $$$v$$$ is when $$$k = cost[v][p]$$$
- $$$memo$$$ means current $$$x$$$ is in range $$$[VL, VR]$$$ so we can use memorization
- $$$save = f[N][p2][p3][p5][p7]$$$ means dp-table the numbers of valid number $$$X$$$ with current states
- $$$l_x$$$ means maximum $$$k$$$ that $$$x^k \leq 10^{18}$$$. Where $$$l2, l3, l5, l7, l10$$$ are such those variables we use
- $$$pw10[x] = 10^x$$$
Notice that - Initially, $$$X = 0$$$, $$$N = 18$$$, $$$(p2, p3, p5, p7)$$$ is such tuple generated by above function
- $$$X = 0$$$ means it is not build yet
- $$$VL \leq X \leq VR$$$ means $$$1 \leq x \times f(x) \leq N$$$
- $$$N = 0$$$ means $$$X$$$ is built completely
- $$$p2 = p3 = p5 = p7 = 0$$$ means $$$f(x) = P$$$
- $$$max(X) < VL$$$ means $$$x \times f(x) < L$$$ always satisfy which is not desired $$$x$$$ we are considering
- $$$min(X) > VR$$$ means $$$x \times f(x) > R$$$ always satisfy which is not desired $$$x$$$ we are considering
- Building such digit $$$v$$$ will reduce each $$$p2, p3, p5, p7$$$ by $$$cost[v][2], cost[v][3], cost[v][5], cost[v][7]$$$
- $$$memo = false$$$ means if we take memorization here, it is not guarantee that $$$1 \leq x \times f(x) \leq N$$$
- $$$save = -1$$$ means this dp-state it is not calculated yet
Ugly precalculation code - O(1)const int l2 = 60, l3 = 37, l5 = 25, l7 = 21, l10 = 19;
ll pw2[l2], pw3[l3], pw5[l5], pw7[l7], 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] = 2 * pw2 [i2 - 1];
for (int i3 = 1; i3 < l3 ; ++i3 ) pw3 [i3] = 3 * pw3 [i3 - 1];
for (int i5 = 1; i5 < l5 ; ++i5 ) pw5 [i5] = 5 * pw5 [i5 - 1];
for (int i7 = 1; i7 < l7 ; ++i7 ) pw7 [i7] = 7 * pw7 [i7 - 1];
for (int i10 = 1; i10 < l10; ++i10) pw10[i10] = 10 * pw10[i10 - 1];
/// 2^a * 3^b * 5^c * 7^d = val
cost[1][2] = 0; cost[1][3] = 0; cost[1][5] = 0; cost[1][7] = 0; /// 0 0 0 0 = 1
cost[2][2] = 1; cost[2][3] = 0; cost[2][5] = 0; cost[2][7] = 0; /// 1 0 0 0 = 2
cost[3][2] = 0; cost[3][3] = 1; cost[3][5] = 0; cost[3][7] = 0; /// 0 1 0 0 = 3
cost[4][2] = 2; cost[4][3] = 0; cost[4][5] = 0; cost[4][7] = 0; /// 2 0 0 0 = 4
cost[5][2] = 0; cost[5][3] = 0; cost[5][5] = 1; cost[5][7] = 0; /// 0 0 1 0 = 5
cost[6][2] = 1; cost[6][3] = 1; cost[6][5] = 0; cost[6][7] = 0; /// 1 1 0 0 = 6
cost[7][2] = 0; cost[7][3] = 0; cost[7][5] = 0; cost[7][7] = 1; /// 0 0 0 1 = 7
cost[8][2] = 3; cost[8][3] = 0; cost[8][5] = 0; cost[8][7] = 0; /// 3 0 0 0 = 8
cost[9][2] = 0; cost[9][3] = 2; cost[9][5] = 0; cost[9][7] = 0; /// 0 2 0 0 = 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{N}$$$ must be satisfied
- Proof: $$$x \times f(x) \leq N \Rightarrow f(x) \times f(x) \leq N \Rightarrow f(x) \leq \sqrt{N}$$$
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{N}$$$ 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{N})$$$. So the complexity is about $$$O(log_2(\sqrt{N}) \times log_3(\sqrt{N}) \times log_5(\sqrt{N}) \times log_7(\sqrt{N})) = O(k(\sqrt{N})) \leq O(log_2(\sqrt{N})^4)$$$
But actually for $$$R \leq 10^{18}$$$, the complexity is just about $$$O(k(\sqrt[4]{N}))$$$
Weak proof - N = 10^kWith (N = 1) -> Found 1 valid tuples || upper_bound 1
With (N = 10) -> Found 3 valid tuples || upper_bound 3
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 50
With (N = 100000) -> Found 83 valid tuples || upper_bound 95
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 414
With (N = 1000000000) -> Found 493 valid tuples || upper_bound 612
With (N = 10000000000) -> Found 694 valid tuples || upper_bound 874
With (N = 100000000000) -> Found 951 valid tuples || upper_bound 1212
With (N = 1000000000000) -> Found 1273 valid tuples || upper_bound 1640
With (N = 10000000000000) -> Found 1670 valid tuples || upper_bound 2172
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: 5701
Weak proof - N = 2^kWith (N = 1) -> Found 1 valid tuples || upper_bound 1
With (N = 2) -> Found 1 valid tuples || upper_bound 1
With (N = 4) -> Found 2 valid tuples || upper_bound 2
With (N = 8) -> Found 2 valid tuples || upper_bound 3
With (N = 16) -> Found 4 valid tuples || upper_bound 4
With (N = 32) -> Found 5 valid tuples || upper_bound 6
With (N = 64) -> Found 8 valid tuples || upper_bound 8
With (N = 128) -> Found 10 valid tuples || upper_bound 11
With (N = 256) -> Found 14 valid tuples || upper_bound 14
With (N = 512) -> Found 17 valid tuples || upper_bound 19
With (N = 1024) -> Found 23 valid tuples || upper_bound 24
With (N = 2048) -> Found 28 valid tuples || upper_bound 30
With (N = 4096) -> Found 36 valid tuples || upper_bound 38
With (N = 8192) -> Found 43 valid tuples || upper_bound 47
With (N = 16384) -> Found 53 valid tuples || upper_bound 58
With (N = 32768) -> Found 63 valid tuples || upper_bound 71
With (N = 65536) -> Found 77 valid tuples || upper_bound 85
With (N = 131072) -> Found 89 valid tuples || upper_bound 102
With (N = 262144) -> Found 106 valid tuples || upper_bound 121
With (N = 524288) -> Found 122 valid tuples || upper_bound 143
With (N = 1048576) -> Found 143 valid tuples || upper_bound 167
With (N = 2097152) -> Found 164 valid tuples || upper_bound 195
With (N = 4194304) -> Found 190 valid tuples || upper_bound 225
With (N = 8388608) -> Found 216 valid tuples || upper_bound 260
With (N = 16777216) -> Found 248 valid tuples || upper_bound 298
With (N = 33554432) -> Found 279 valid tuples || upper_bound 339
With (N = 67108864) -> Found 317 valid tuples || upper_bound 386
With (N = 134217728) -> Found 355 valid tuples || upper_bound 437
With (N = 268435456) -> Found 400 valid tuples || upper_bound 492
With (N = 536870912) -> Found 446 valid tuples || upper_bound 553
With (N = 1073741824) -> Found 498 valid tuples || upper_bound 620
With (N = 2147483648) -> Found 553 valid tuples || upper_bound 692
With (N = 4294967296) -> Found 614 valid tuples || upper_bound 770
With (N = 8589934592) -> Found 679 valid tuples || upper_bound 855
With (N = 17179869184) -> Found 749 valid tuples || upper_bound 946
With (N = 34359738368) -> Found 825 valid tuples || upper_bound 1045
With (N = 68719476736) -> Found 905 valid tuples || upper_bound 1152
With (N = 137438953472) -> Found 991 valid tuples || upper_bound 1266
With (N = 274877906944) -> Found 1083 valid tuples || upper_bound 1388
With (N = 549755813888) -> Found 1181 valid tuples || upper_bound 1520
With (N = 1099511627776) -> Found 1286 valid tuples || upper_bound 1660
With (N = 2199023255552) -> Found 1398 valid tuples || upper_bound 1810
With (N = 4398046511104) -> Found 1517 valid tuples || upper_bound 1970
With (N = 8796093022208) -> Found 1646 valid tuples || upper_bound 2140
With (N = 17592186044416) -> Found 1780 valid tuples || upper_bound 2321
With (N = 35184372088832) -> Found 1924 valid tuples || upper_bound 2513
With (N = 70368744177664) -> Found 2074 valid tuples || upper_bound 2717
With (N = 140737488355328) -> Found 2235 valid tuples || upper_bound 2933
With (N = 281474976710656) -> Found 2402 valid tuples || upper_bound 3161
With (N = 562949953421312) -> Found 2581 valid tuples || upper_bound 3403
With (N = 1125899906842624) -> Found 2767 valid tuples || upper_bound 3658
With (N = 2251799813685248) -> Found 2966 valid tuples || upper_bound 3928
With (N = 4503599627370496) -> Found 3174 valid tuples || upper_bound 4212
With (N = 9007199254740992) -> Found 3393 valid tuples || upper_bound 4511
With (N = 18014398509481984) -> Found 3625 valid tuples || upper_bound 4826
With (N = 36028797018963968) -> Found 3866 valid tuples || upper_bound 5157
With (N = 72057594037927936) -> Found 4121 valid tuples || upper_bound 5505
With (N = 144115188075855872) -> Found 4386 valid tuples || upper_bound 5870
With (N = 288230376151711744) -> Found 4665 valid tuples || upper_bound 6253
With (N = 576460752303423488) -> Found 4955 valid tuples || upper_bound 6655
With (N = 1152921504606846976) -> Found 5260 valid tuples || upper_bound 7076
Error: 23112
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;
}
const double EPS = 0.0188704;
int main()
{
freopen("Test.OUT", "w", stdout);
double error = 0;
ll mul = 2;
ll over = (1LL << 62) / mul;
for (ll t = 1; t < over; t *= mul)
{
L = 1;
R = t;
lim = sqrt(R);
int res = solve();
double base = log(sqrt(sqrt(R))) + 1;
int complexity = ceil(EPS + (base / log(2)) * (base / log(3)) * (base / log(5)) * (base / log(7)));
cout << "With (N = " << R << ") -> Found " << res << " valid tuples || upper_bound " << complexity << endl;
int delta = complexity - res;
if (delta < 0)
{
cout << "Program failed at (t = " << t << ") -> ";
cout << "Returning " << res << " compared to " << complexity << endl;
exit(0);
}
else error += delta;
}
cout << "Error: " << error;
return 0;
}
About the complexity:
- $$$O(h(x)) = O(log_{10}(N))$$$ is number of digits we have to build
- $$$O(k(x)) = O(log_2(N) \times log_3(N) \times log_5(N) \times log_7(N)) = O(log(N)^4)$$$ is product of all prime digits $$$p$$$ with its maximum power $$$k$$$ satisfy $$$p^k \leq N$$$
- $$$O(g(x)) = O(k(\sqrt{N}))$$$ is number of such valid tuples, but for $$$1 \leq N \leq 10^{18}$$$ it is about $$$\approx O(k(\sqrt[4]{N})) \leq O(log_2^4{\sqrt[4]{N}})$$$
- The space complexity is $$$O(SPACE) = O(h(x) \times k(x)) = O(log_2(N) \times log_3(N) \times log_5(N) \times log_7(N) \times log_{10}(N)) = O(log(N)^5)$$$
- The time complexity is $$$O(TIME) = O(SPACE) + O(g(x) \times k(x)) \approx O(log(N)^4 \times log_2^4{\sqrt[4]{N}})$$$
Other
About the real complexity for $$$O(k(x))$$$, do you find a better/closer upper bound of counting such tuples of $$$(a, b, c, d \in \mathbb{N})$$$ that $$$P = 2^a \times 3^b \times 5^c \times 7^d \leq N$$$ ? Since my $$$O(log_2(N))$$$ complexity seem very far than the real counting and $$$O(log_2(\sqrt{N}))$$$ is closer but just correct for $$$N \leq 10^{18}$$$
Thanks for reading and sorry for updating this blog publicly so many times (most is for the proving path and correcting the complexity)
Not really sure, but isnt that f(x)<x, therefore we only need to consider f(x)<=sqrt(10^9)?
Yes your way is correct ^^, thank sir. I have just got accepted from the problem and I am writting the solution
I have just done the problem and wrote the solution, thanks for reading ^^
If you have a better explaination/implementation or better complexity, please comment in this post too ^^.
By the way, if you guys are interesting, here is the Vietnamese version of the problem where we need to count such valid numbers in range $$$[A..B]$$$ where $$$1 \leq A \leq B \leq 10^{18}$$$. And here is the Editorial in Vietnamese
Wow, that's an amazing problem
That's your problem...
No, that's just the same name