Hướng dẫn cho Điểm Hoàn Hảo

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

<button style="text-align:center; font-size:30px; color:none; background:none; border:none; padding:0; position:relative; left:38.5%;">
$\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.9}}}}}$
</button>

$\color{#ff7500}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}$ $\color{#ff7500}{\text{Và sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu với thuật của mình và thu được bài học cho mình}}$ $\color{#ff7500}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}$ [ở đây](https://www.facebook.com/SPectiar2k/)

<button style="text-align:center; font-size:30px; color:none; background:none; border:none; padding:0; position:relative; left:38.5%;">
$\color{orange}{\text{Mục lục}}$
</button>

$\color{#300000}{\text{1. Hướng dẫn cày trâu}}$

$\color{#903030}{\text{<Nhận xét>}}$ Vì khi $x > R$ có $x \times f(x) > R$ nên ta chỉ quan tâm các $x \in [1, R]$
$\color{#903030}{\text{<Mục tiêu>}}$ Gọi $f(x)$ là tích các ước của $x$. Mình cần đếm số lượng $x \in [1, R]$ thỏa $L \leq x \times f(x) \leq R$
$\color{#903030}{\text{<Độ phức tạp>}}$ $O(R\ \times\ log_{10}(R))$ thời gian

Tính $f(x)$ phải duyệt qua các chữ số nên mất $O(log_{10}(x))$

Mình phải thử $O(R)$ số $x$ trong đoạn $[1, R]$ nên mất $O(R)$

$\color{#c01515}{\text{1. Tiếp cận cày trâu}}$

$\color{#f03030}{\text{Tính } f(x)}$ Ta tiếp tục nhân kết quả hiện tại với chữ số cuối của $x$ và xóa chữ số ấy trong khi $x > 0$

Khỏi tạo ban đầu $res = 1$

Nhân với chữ số cuối của $x$ bằng $res = res \times (x\mod10)$ (C++ là res *= x % 10)

Xóa chữ số cuối của $x$ bằng $x = \lfloor \frac{x}{10} \rfloor$ (C++ là x /= 10)

$\color{#f03030}{\text{Đếm kết quả}}$ Duyệt các $x \in [1, R]$ và tăng biến đếm khi $x \times f(x) \in [L, R]$

$\color{#009933}{\text{1. Code tham khảo }}$: Cày trâu

$^{^{\color{#7f5f3f}{\text{Độ phức tạp : }} O(R\ \times\ log_{10}(R))\ \color{#7f5f3f}{\text{thời gian}}\ ||\ O(1)\ \color{#7f5f3f}{\text{bộ nhớ}}}}$

C++

/// cal(x) = x * f(x)
ll cal(ll x, ll lim)
{
    ll res = x;
    do {
        int t = x % 10;
        if (res > lim / t) return -1; /// (x * f(x) > R)
        res *= t;
    } while (x /= 10);
    return res;
}

ll brute(ll l, ll r)
{
    ll res = 0;
    for (ll x = 1; x <= r; ++x)
        res += cal(x, n) >= l; /// L <= x * f(x) <= R

    return res;
}

$\color{#300000}{\text{2. Hướng dẫn nhánh cận}}$

$\color{#903030}{\text{<Nhận xét 1>}}$ Nếu $x$ chứa chữ số $0$ thì $f(x) = 0$ $\Rightarrow$ $x \times f(x) < L$
$\color{#903030}{\text{<Nhận xét 2>}}$ Nếu $(x > R)$ hoặc $(f(x) > R)$ thì $(x \times f(x) > R)$
$\color{#903030}{\text{<Nhận xét 3>}}$ Nếu $x * f(x) > R$ thì $(x + 1) * f(x + 1) > R$
$\color{#903030}{\text{<Mục tiêu>}}$ Thử dựng từng chữ số cho $x$, sao cho $x$ không chứa chữ số $0$. Bỏ qua khi $x > R$ và tăng biến đếm khi $x \geq L$
$\color{#903030}{\text{<Độ phức tạp>}}$ $O(result + log_{10}(L))$ thời gian

Mọi số không thỏa mãn đều đã bị loại ngay bởi nhánh cận, và có $O(log_{10}(L))$ số $x < L$

Những số còn lại là các giá trị thỏa mãn sẽ được tăng biến đếm, sẽ là $O(result)$

Ngoài ra còn tốn thêm $O(log_{10}(R))$ độ sâu đệ quy bằng stack

$\color{#c01515}{\text{2. Tiếp cận}}$

$\color{#f03030}{\text{<Hàm đệ quy> }}$ $build(X, Y, T)$ có nghĩa là đang xây từ giá trị $X$, có $f(X) = Y$ và $X * f(X) = T$

Nếu $X \geq L$ thì tăng biến đếm

Ta sẽ thử chèn từng chữ số $v \in [1, 9]$ vào sau $X$ (Trong C++ là X = 10 * X + v) (Nhận xét 1)

Tính giá trị của $f(X)$ khi chèn thêm $v$ vào (Trong C++ là Y = Y * v)

Tính giá trị của $T = X * Y$, nếu $T > R$ thì kết thúc vòng lặp (Nhận xét 2 & 3)

$\color{#009933}{\text{2. Code tham khảo}}$: Tiếp cận

$^{^{\color{#7f5f3f}{\text{Độ phức tạp : }} O(result + log_{10}(L))\ \color{#7f5f3f}{\text{thời gian}}\ ||\ O(log_{10}(R))\ \color{#7f5f3f}{\text{bộ nhớ}}}}$

C++

/// 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 (L >= 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 > R) break;  /// x * f(x) > N
        build(NX, NY, NT);
    }
}

$\color{#300000}{\text{3. Hướng dẫn thuật hoàn chỉnh}}$

$\color{#903030}{\text{<Nhận xét 1>}}$ $\forall x \in \mathbb{N}, f(x) \leq x$

Chứng minh: $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)$

$\color{#903030}{\text{<Nhận xét 2>}}$ Nếu $x$ thỏa thì $f(x) \leq \sqrt{R}$

Chứng minh: $x \times f(x) \leq R \Rightarrow f(x) \times f(x) \leq R \Rightarrow f(x) \leq \sqrt{R}$

$\color{#903030}{\text{<Nhận xét 3>}}$ $\exists\ a, b, c, d \in \mathbb{N} \rightarrow f(x) = 2^a \times 3^b \times 5^c \times 7^d$

$x = \overline{\dots dcba}$ $\Rightarrow$ $(0 \leq \dots, d, c, b, a \leq 9)$ và $f(x) = \dots \times d \times c \times b \times a$

Mà ta cũng có $\forall$ chữ số $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$

Và $f(x)$ là tích các chữ số của $x$ $\Rightarrow$ điều phải chứng minh

$\color{#903030}{\text{<Nhận xét 4>}}$ Số lượng bộ 4 số $(a, b, c, d)$ để $P = 2^a \times 3^b \times 5^c \times 7^d \leq \sqrt{R}$ là rất nhỏ

Số mũ của các thừa số nguyên tố $2, 3, 5, 7$ tối đa có thể lấy là $O(log_2(\sqrt{R})), O(log_3(\sqrt{R})), O(log_5(\sqrt{R})), O(log_7(\sqrt{R}))$

Vậy độ phức tạp để tìm là $O(log_2(\sqrt{R}) \times log_3(\sqrt{R}) \times log_5(\sqrt{R}) \times log_7(\sqrt{R})) \leq O(log_2^4(\sqrt{R})$

Với $R = 10^9$ thì có 493 bộ, $R = 10^{18}$ thì có 5914 bộ

$\color{#903030}{\text{<Nhận xét 5>}}$ Thay vì thử từng $x$ để tính $f(x)$ và kiểm tra thì làm điều ngược lại tốt hơn

Nếu thử từng số $x$ thì mình có nhiều trường hợp cần xét

Thay vào đó bằng việc duyệt qua số ít các $f(x)$ ta sẽ quy về bài toán nhỏ hơn và xét ít trường hợp hơn

$\color{#903030}{\text{<Nhận xét 6>}}$ Khi ta biết trước $f(x)$, ta có thể tìm các $x$

Chứng minh: Vì $f(x)$ là tích các chữ số được tạo từ các thừa số chữ số nguyên tố 2, 3, 5, 7 nên $x$ cũng tạo được các chữ số từ bằng tích một số thừa số nguyên tố đó

$\color{#903030}{\text{<Mục tiêu>}}$ Với mõi $P = 2^a \times 3^b \times 5^c \times 7^d \leq \sqrt{R}$, đếm số lượng số có $f(x) = P$

Có được giá trị $f(x) = P$ nên $VL \leq x \leq VR$ với $VL = \lceil \frac{L}{P} \rceil$ và $VR = \lfloor \frac{R}{P} \rfloor$

Và từ nhận xét 6, ta có thể dùng quy hoạch động chữ số để giải bài

$\color{#c01515}{\text{3. Tiếp cận}}$

$\color{#f03030}{\text{<Mục tiêu>}}$ Thử xây dựng từng chữ số của $X$. Vì $X \leq R \leq 10^{18}$ nên ta cần xây khoảng 18 chữ số
$\color{#f03030}{\text{<Hàm đệ quy>}}$ Ta sẽ tạo một hàm đệ quy $magic(X, N, p2, p3, p5, p7)$, trong đó

$VL, VR$ là đoạn cần xét các giá trị $x$ để $L \leq x \times f(x) \leq R$

Số đang xét có tiền tố các chữ số là giá trị $X$

Cần phải xét thêm $N$ chữ số phía sau $X$

$p2, p3, p5, p7$ là lượng thừa số nguyên tố còn lại của $f(x)$

$min(X, N) = X \times 10^N = \overline{X\underbrace{00000\dots}_{N}}$ là giá trị nhỏ nhất có thể tạo với tiền tố $X$ và thêm $N$ chữ số vào phía sau

$max(X, N) = X \times 10^N + 10^N - 1 = \overline{X\underbrace{99999\dots}_{N}}$ là giá trị lớn nhất có thể tạo với tiền tố $X$ và thêm $N$ chữ số vào phía sau

$cost[v][p]$ là ước lớn nhất $p^k$ trong $v$ là khi $k = cost[v][p]$

$memo$ nghĩa là hiện tại $x$ đang nằm trong đoạn $[VL, VR]$ nên ta có thể dùng nhớ

$save = f[N][p2][p3][p5][p7]$ là bảng quy hoạch động tính số lượng số thỏa mãn với tiền tố $X$ và trạng thái hiện tại

$l_x$ là giá trị $k$ lớn nhất để $x ^ k \leq 10^{18}$. Trong hàm dưới sử dụng các biến $l2, l3, l5, l7, l10$ với mục đích tương tự

$pw10[x] = 10^x$

$\color{#f03030}{\text{<Tính toán>}}$

Khởi tạo $X = 0$, $N = 18$, $(p2, p3, p5, p7)$ là bộ 4 thỏa mãn

$X = 0$ nghĩa là chưa bắt đầu xây số $X$

$VL \leq X \leq VR \Leftrightarrow L \leq x \times f(x) \leq R$

$N = 0$ nghĩ là đã xây xong số $X$

$p2 = p3 = p5 = p7 = 0$ nghĩa là $f(X) = P$

$max(X) < VL$ có nghĩa là dù thêm sau $X$ kiểu gì thì giá trị cũng nằm ngoài vùng cần xét ($X < L$)

$min(X) > VR$ có nghĩa là dù thêm sau $X$ kiểu gì thì giá trị cũng nằm ngoài vùng cần xét ($X > R$)

Việc xây thêm chữ số $v$ giảm đi các giá trị $p2, p3, p5, p7$ một lượng bằng $cost[v][2], cost[v][3], cost[v][5], cost[v][7]$

$memo = false$ có nghĩa là nếu ta thêm nhớ ở đây thì không đảm bảo điều kiện $L \leq x \times f(x) \leq R$

$save = -1$ có nghĩa là trạng thái hiện tại chưa được tính

$\color{#f03030}{\text{<Độ phức tạp>}}$

$O(h(x)) = O(log_{10}(R))$ là số lượng chữ số cần xây

$O(k(x)) = O(log_2(R) \times log_3(R) \times log_5(R) \times log_7(R)) \leq O(log_2(R)^4)$ là tích các chữ số nguyên tố $p$ với số mũ tối đa $k$ thỏa $p^k \leq N$

$O(g(x)) = O(k(\sqrt{R})) \leq O(log_2^4(\sqrt{R}))$ là số lượng bộ 4 thỏa mãn, nhưng với $N$ nhỏ thì $O(g(x)) \approx O(k(\sqrt[4]{R})) \leq O(log_2^4(\sqrt[4]{R}))$

Độ phức tạp bộ nhớ là $O(SPACE) = O(h(x) \times k(x)) \approx O(log(R)^5)$

Độ phức tạp thời gian là $O(TIME) = O(SPACE) + O(g(x) \times k(x)) \approx O(log_2^4(\sqrt[4]{R}) \times log_2(R)^4)$

$\color{#009933}{\text{3. Code tham khảo<Accepted> }}$: Tiếp cận

$^{^{\color{#7f5f3f}{\text{Độ phức tạp : }} O(log_2^4(\sqrt[4]{R}) \times log_2(R)^4)\ \color{#7f5f3f}{\text{thời gian}}\ ||\ O(log(R)^5)\ \color{#7f5f3f}{\text{bộ nhớ}}}}$

C++

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
}

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; /// Invalid factors
    if (N == 0) return (p2 + p3 + p5 + p7 == 0) && (VL <= X && X <= VR); /// Valid number

    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); /// Continue build X with zeros
    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;
}

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

Bình luận

17

SPyofgame 10:42 p.m. 5 Tháng 11, 2020 ← đã chỉnh sửa →

English Version of the editorial -> (https://codeforces.com/blog/entry/84354)

1 phản hồi

Hướng dẫn cho Điểm Hoàn Hảo

\(\color{#300000}{\text{1. Hướng dẫn cày trâu}}\)

\(\color{#c01515}{\text{1. Tiếp cận cày trâu}}\)

\(\color{#009933}{\text{1. Code tham khảo }}\): Cày trâu

\(^{^{\color{#7f5f3f}{\text{Độ phức tạp : }} O(R\ \times\ log_{10}(R))\ \color{#7f5f3f}{\text{thời gian}}\ ||\ O(1)\ \color{#7f5f3f}{\text{bộ nhớ}}}}\)

\(\color{#300000}{\text{2. Hướng dẫn nhánh cận}}\)

\(\color{#c01515}{\text{2. Tiếp cận}}\)

\(\color{#009933}{\text{2. Code tham khảo}}\): Tiếp cận

\(^{^{\color{#7f5f3f}{\text{Độ phức tạp : }} O(result + log_{10}(L))\ \color{#7f5f3f}{\text{thời gian}}\ ||\ O(log_{10}(R))\ \color{#7f5f3f}{\text{bộ nhớ}}}}\)

\(\color{#300000}{\text{3. Hướng dẫn thuật hoàn chỉnh}}\)

\(\color{#c01515}{\text{3. Tiếp cận}}\)

\(\color{#009933}{\text{3. Code tham khảo<Accepted> }}\): Tiếp cận

\(^{^{\color{#7f5f3f}{\text{Độ phức tạp : }} O(log_2^4(\sqrt[4]{R}) \times log_2(R)^4)\ \color{#7f5f3f}{\text{thời gian}}\ ||\ O(log(R)^5)\ \color{#7f5f3f}{\text{bộ nhớ}}}}\)

Bình luận