# qvsick

Tóm tắt: Gọi $f(x)$ là tích các chữ số của $x$. Tính số số $x$ có $a \leq x \times f(x) \leq b$ $(1 \leq a \leq b \leq 10^{18})$

Nhận xét $f(x) \leq x$. Vì các thừa số trong $f(x)$ chỉ tối đa đến 9. Còn các thừa số trong $x$ $(x=10^{n-1} \times x_{n-1}+...)$ thì lớn hơn. Theo giới hạn ta có $x \times f(x) \leq 10^{18} \Rightarrow f(x) \leq 10^9$. Vì nếu $A \times B \leq N$ thì $min(A,B) \leq \sqrt{N}$

Nhận xét với $x$ không chứa bất kì chữ số $0$ nào thì $f(x) = 2^a \times 3^b \times 5^c \times 7^d$ (vì $f(x)$ là tích của các số $\leq 9$). Với giới hạn trên ta có thể duyệt mọi bộ $(a,b,c,d)$ để tính ra tất cả các số có thể là $f(x)$. Vì $f(x) \leq 10^9$ nên thực nghiệm cho thấy chỉ có khoảng $5200$ số thoả mãn.

Ta duyệt mọi $f(x)$ có thể. Ta có $a \leq x \times f(x) \leq b \Rightarrow \lceil \frac{a}{f(x)} \rceil \leq x \leq \lfloor \frac{b}{f(x)} \rfloor$. Bài toán quy về đếm số số thuộc một miền xác định và có tích các chữ số bằng một số cho trước. Ta có số số thoả mãn trong đoạn $[L,R]$ bằng số số thoả mãn $\leq R$ - số số thoả mãn $\leq (L-1)$. Do đó lời giải sau đây sẽ chỉ giải quyết việc đếm số số thoả mãn nhỏ hơn hoặc bằng cận trên $R$

Ta dùng quy hoạch động chữ số. Gọi $f(i,smaller,zeros,prod)$ là số các số khi:

- xét đến chữ số thứ $i$
- số hiện tại đã chắc chắn nhỏ hơn cận trên chưa
- số hiện tại đã chắc chắn khác $0$ chưa
- hiện tại đang cần tích các chữ số là $prod$

Xuất phát từ trạng thái $(n-1,0,0,P)$ với $P$ là $f(x)$ hiện tại đang xét và $n-1$ là độ dài của $R$ $(R_{n-1}...R_0)$ Với mỗi vị trí $i$, ta thử điền các chữ số từ 0 đến 9 và chuyển sang trạng thái mới như sau:
- nếu $i<0$ thì trả về $1$ nếu $prod=1$ và $zeros=true$
- ngược lại, duyệt các chữ số $d$ từ 0 đến 9 để điền vào vị trí $i$:
- nếu $smaller=false$ và $d>R_i$ thì không chuyển
- ngược lại, ta có $nsmaller$ là trạng thái $smaller$ mới. nếu $d<R_i$ hoặc $smaller=true$ thì $nsmaller=true$. nếu điền $d=0$:
- $zeros=false$ thì các chỉ số $zeros,prod$ giữ nguyên. ta chuyển sang trạng thái $(i-1,nsmaller,zeros,prod)$ còn không thì cũng không chuyển.
- nếu $d>0:$ nếu $prod$ không chia hết cho $d$ thì không chuyển, còn không thì:
- chuyển sang trạng thái $(i-1,nsmaller,nzeros,nprod)$ với $nzeros=true$ và $nprod=prod/d$

Vì chiều $prod$ có thể rất lớn, lên đến $10^9$ nhưng số lượng thì rất ít (5200 - số bộ $f(x)$ có thể). Do đó ta có thể lưu mảng $DP$ bằng map/unordered_map hoặc lưu bằng mảng thường và chặt nhị phân để tìm chỉ số của $prod$ trong mảng lưu các số có thể là $f(x)$.

Để cho tiện thì ta chỉ lưu các trạng thái dp mà $smaller=true$ và $zero=true$. Khi đó độ phức tạp là (số trạng thái + (số bộ $f(x)$ $\times$ độ dài của một số)) $\times$ chi phí chuyển. Vì khi xét đến vị trí thứ $i$, để $smaller=false$ thì toàn bộ prefix phía trước nó phải trùng với prefix của cận trên. Tương tự, để $zeros=false$, thì toàn bộ prefix của $i$ ta phải điền số $0$. Vậy số trạng thái có $smaller=false$ hoặc $zeros=false$ là độ dài số ta đang xét. Từ đó, các trạng thái dp cần lưu lại ta chỉ cần tính một lần xuyên suốt chương trình, còn các trạng thái không cần lưu thì chỉ cần tính lại từ đầu với độ phức tạp nhỏ hơn.

## Code

https://ideone.com/0i676T