# Help Conan 10! - Solution

## 1. Quan sát

Theo đề bài, chúng ta cần tìm số các số $x$ thỏa mãn:
$$A <= x * f(x) <= B$$

với $f(x)$ là tích các chữ số của $x$.

$$ {A \over f(x)} <= x <= {B \over f(x)} $$

Dễ thấy rằng do $A >= 1$ nên $x \ne 0$ và $f(x) \ne 0$, suy ra mọi số $x$ thỏa mãn sẽ không chứa chữ số $0$ $(1)$

Do tích các chữ số của một số luôn nhỏ hơn hoặc bằng chính số đó nên $f(x) <= x$, suy ra

$$f(x)^2 <= x * f(x) <= 1e18$$ hay $f(x) <= 1e9$ $(2)$

Vì $f(x)$ ở đây là tích các chữ số từ $[1, 9]$ nên:
$$f(x) = 1^a . 2^b . 3^c . 4^d . 5^e . 6^f . 7^g . 8^h . 9^i = 2^{a_1} . 3^{a_2} . 5^{a_3} . 7^{a_4} (3)$$

Kết hợp cùng nhận xét $(2)$, nếu for qua 4 vòng ta nhận thấy rằng chỉ có đúng $5194$ bộ số $a_1, a_2, a_3, a_4$ phân biệt thỏa mãn điều kiện trên, ta hoàn toàn có thể lưu trước $5194$ tích đó thành một mảng.

Giờ đây bài toán rút gọn về:

- Với mỗi tích $f(x)$, cho $A' = {A \over f(x)}$, $B' = {B \over f(x)}$, có bao nhiêu số $x$ thỏa mãn:

$$A' <= x <= B'$$

## 2. Thuật trâu

Dễ thấy rằng ta có thể chạy 1 vòng từ $A'$ đến $B'$ rồi đếm xem có bao nhiêu số thỏa mãn. Tuy nhiên $x <= 1e18$ là quá lớn nên cách này sẽ TLE.

## 3. Lời giải

Đây là một biến thể của bài toán: Đếm số các số có tích các chữ số bằng $k$, vì giới hạn của bài là $1e18$, nên sẽ chỉ có tối đa $18$ chữ số, mỗi chữ số có $9$ cách chọn (từ nhận xét $(1)$).

Ta có thể sử dụng kỹ thuật **Digit DP** để xử lý bài toán này, gọi **dp[n][product]** là số các số có **n** chữ số và tích các chữ số bằng **product**, do tích các chữ số của một số có thể rất lớn nên từ nhận xét $(3)$, ta có thể tách bớt ra thành **dp[n][a1][a2][a3][a4]**.

Ta có thể giải quyết mỗi bài toán dp trên bằng đệ quy: **solve(n, num, num_digit)** là số các số thỏa mãn có **n** chữ số, **num** lưu số ta đã chọn ở lần đệ quy trước và **num_digit** lưu số vị trí còn nhét được thêm.

Độ phức tạp: $O(5194 * g(B))$ với $g(B) =$ số chữ số của $B$.

## Code:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn = 2e5 + 5;
const ll maxn_sqrt = 1e9;
const ll maxn_ll = 1e18;
const ll mod = 1e9 + 7;

ll binpow(ll a, ll b)
{
    ll r = 1;

    for (;b; a = a * a, b >>= 1)  if (b & 1) r = r * a; return r;
}
ll dp[19][30][30][30][30];
ll ans = 0;
ll current[4] = {0, 0, 0, 0};
// 2^a1 * 3^a2 * 5^a3 * 7^a4
ll base[10][4] = 
{
   {0, 0, 0, 0}, // 1
   {0, 0, 0, 0}, // 1
   {1, 0, 0, 0}, // 2
   {0, 1, 0, 0}, // 3
   {2, 0, 0, 0}, // 4
   {0, 0, 1, 0}, // 5
   {1, 1, 0, 0}, // 6
   {0, 0, 0, 1}, // 7
   {3, 0, 0, 0}, // 8
   {0, 2, 0, 0}  // 9
};

bool validate(ll min_num, ll max_num, ll l, ll r)
{
	if (min_num >= l && max_num <= r) return true;
	return false;
}

ll solve(ll n, ll num, ll num_digit, ll l, ll r)
{
	if (num > r || (num + num_digit - 1) < l) return 0;
	if (n >= 18) 
	{
		//cout << current[0] << ' ' << current[1] << ' ' << current[2] << ' ' << current[3] << '\n';
		return !current[0] && !current[1] && !current[2] && !current[3];
	}
	
	if (validate(num, (num + num_digit - 1), l, r) && dp[n][current[0]][current[1]][current[2]][current[3]] != -1) return dp[n][current[0]][current[1]][current[2]][current[3]];
	// kiểm tra trường hợp số đang xét có quá khoảng l r cần biết không (max là nhét thêm toàn chữ số 9 vào)
	ll cnt = 0;
	ll start;
	if (num == 0) start = 0;
	else start = 1;
	
	for (ll i = start; i <= 9; ++i)
	{
		bool flag = true; 
		for (ll j = 0; j < 4; ++j)
		{
			if (base[i][j] > current[j])
			{
				flag = false;
				break;
			}	
		}	
		if (!flag) continue;
		
		for (ll j = 0; j < 4; ++j) current[j] -= base[i][j]; // Giảm số mũ của chữ số đã chọn xuống
		ll addnew_num = (i * (num_digit / 10));
		cnt += solve(n + 1, num + addnew_num, (num_digit / 10), l, r); // Nhét chữ số đã chọn và đệ quy đến trường hợp nhỏ hơn tiếp theo
                                                                       
		for (ll j = 0; j < 4; ++j) current[j] += base[i][j]; //Reset lại số mũ lũy thừa về base case ban đầu, xét các chữ số tiếp theo
	}
	
	if (validate(num, (num + num_digit - 1), l, r)) 
	{
		dp[n][current[0]][current[1]][current[2]][current[3]] = cnt; // lưu trường hợp đệ quy vào dp
		return dp[n][current[0]][current[1]][current[2]][current[3]]; 
	}
	else return cnt;
	
}

int main()
{
	memset(dp, -1, sizeof(dp));
	ll l, r;
	cin >> l >> r;

    //tính hết mọi bộ số có tích thỏa mãn
    //do chỉ có 5194 tích thỏa mãn nên lưu trước vào một mảng riêng hoặc gen bằng đệ quy cũng được
    for (ll i = 0; i <= 30; ++i)
    {
        for (ll j = 0; j <= 30; ++j)
        {
            for (ll k = 0; k <= 30; ++k)
            {
                for (ll q = 0; q <= 30; ++q)
                {
                    ll n = binpow(2, i) * binpow(3, j) * binpow(5, k) * binpow(7, q);
                    if (n <= maxn_sqrt && n > 0) 
                    {
                        current[0] = i;
                        current[1] = j;
                        current[2] = k;
                        current[3] = q;
                        // do x có thể bé hơn n (x / n = 0)
                        ans += solve(0, 0, maxn_ll, (l + n - 1) / n, r / n); // a/x <= x <= b/x
                        //cout << n << '\n';

                    }
                }
            }
        }
    }
	cout << ans << '\n';
}