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≤x∗f(x)≤N
Example: For N=20, there are 5 valid numbers 1,2,3,4,11
The limitation
- Subtask 1: N≤106
- Subtask 2: N≤1010
- Subtask 3: N≤1014
- Subtask 4: N≤1018
My approach for subtask 1
- If (x>N) or (f(x)>N) then (x∗f(x)>N). So we will only care about x≤N that x∗f(x)≤N
My approach for subtask 2
- If x contains 0 then f(x)=0⇒x×f(x)<1. We only care about such x without 0 digit
Here is the solution:
Let takes some x satisfy 1≤x∗f(x)≤N
We can easily prove that f(x)≤x, and because x∗f(x)≤N, we have f(x)≤√N (notice that x might bigger than √N)
Since f(x) is product of digits of x, which can be obtain by such digits {1,2,…,9}. So f(x)=2a×3b×5c×7d
So we can bruteforces all possible tuple of such (a,b,c,d) satisfy (P=2a×3b×5c×7d≤√N). There are small amount of such tuples (493 tuples for N=109 and 5914 tuples for N=1018)
For each tuples, we need to counting the numbers of such x that 1≤x×f(x)≤N and f(x)=P.
- We have the value P, so ⌈1P⌉≤x≤⌊NP⌋.
- 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≤x≤R) whose f(x)=P
Solving Subproblem
We try to build each digits by digits for X. Because X≤N, so we have to build about 18 digits.
Lets make a recursive function magic(X,N,p2,p3,p5,p7)
About the proving stuff
1) ∀x∈N,f(x)≤x
- Proof: x=¯…dcba=⋯+d×103+c×102+b×101+a×100≥⋯×d×c×b×a=f(x)
2) If x satisfy then f(x)≤√R must be satisfied
- Proof: x×f(x)≤R⇒f(x)×f(x)≤R⇒f(x)≤√R
3) ∃ a,b,c,d∈N→f(x)=2a×3b×5c×7d
Since x=¯…dcba⇒(0≤…,d,c,b,a≤9) and f(x)=⋯×d×c×b×a
And we also have ∀ digit v (v∈N,0≤v≤9) →∃ a,b,c,d∈N→v=2a×3b×5c×7d
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∈[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=2a×3b×5c×7d≤√R is very small
Lets O(k(x))=O(log2(x)×log3(x)×log5(x)×log7(x))
Since each value x have the upper bound of logx(√R). So the complexity is about O(log2(√R)×log3(√R)×log5(√R)×log7(√R))=O(k(√R))≤O(log2(√R)4)
But actually for R≤1018, the complexity is just about O(k(4√R))
About the complexity:
- O(h(x))=O(log10(R)) is number of digits we have to build
- O(k(x))=O(log2(R)×log3(R)×log5(R)×log7(R))=O(log(R)4) is product of all prime digits p with its maximum power k satisfy pk≤N
- O(g(x))=O(k(√R)) is number of such valid tuples, but for 1≤N≤1018 it is about ≈O(k(4√R))≤O(log424√R)
- The space complexity is O(SPACE)=O(h(x)×k(x))=O(log2(R)×log3(R)×log5(R)×log7(R)×log10(R))=O(log(R)5)
- The time complexity is O(TIME)=O(SPACE)+O(g(x)×k(x))≈O(log(R)4×log424√R)
Other
- Here is the Vietnamese version of the problem where we need to count such valid numbers in range [A..B] where 1≤A≤B≤1018. (Vietnamese Editorial)
- Does anyone know the real complexity for O(k(x)) ? — Counting such tuples of (a,b,c,d∈N) that P=2a×3b×5c×7d≤N ?
Since my O(log2(N)) complexity seem very far than the real counting and O(log2(√N)) is closer but just correct for N≤1018
- Thanks for reading and sorry for updating this blog publicly so many times