\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\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{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hướng dẫn}}\)

• Subtask 1: Nếu tồn tại \(k \in \mathbb{N}\) để \(c = ku\) thì xuất \(k\) ngược lại xuất \(-1\)

• Subtask 2: Chia dần \(c\) cho \(u\), \(o\), \(m\) đến khi không chia được nữa. Nếu sau cùng \(c = 1\) thì xuất số lần chia, ngược lại xuất \(-1\)

• Subtask 3: Thử gọi đệ quy chia \(c\) cho \(u\) và \(m\). Nếu tồn tại cách chia để \(c = 1\) thì xuất số lần chia ít nhất, ngược lại xuất \(-1\)

• Subtask 4: Thử gọi đệ quy chia \(c\) cho \(u\), \(o\) và \(m\). Nếu tồn tại cách chia để \(c = 1\) thì xuất số lần chia ít nhất, ngược lại xuất \(-1\)

\(\color{goldenrod}{\text{Tiếp cận}}\)

• Subtask 1: Toán

Chia dần \(c\) cho \(u\) đến khi không chia được nữa. Nếu \(c = 1\) thì xuất số lần chia, ngược lại xuất -1

Độ phức tạp thời gian là \(O(log_u(c))\)

• Subtask 2: Toán

Chia dần \(c\) cho \(u\), \(o\), \(m\) đến khi không chia được nữa. Nếu \(c = 1\) thì xuất số lần chia, ngược lại xuất -1

Độ phức tạp thời gian là \(O(log_u(c) + log_o(c) + log_m(c))\)

• Subtask 3: Trâu hoặc Quy hoạch động

Gọi \(f(x)\) là kết quả của bài toán với \(x = c\)

Trường hợp \(x = 1\) thì trả về \(1\)

Trường hợp \(x\) chia hết cho \(u\) thì tính kết quả của \(f(\frac{x}{u})\)

Trường hợp \(x\) chia hết cho \(m\) thì tính kết quả của \(f(\frac{x}{m})\)

Trả về giá trị min của 2 giá trị trên hoặc trả về -1 khi không chia hết cho cả 2 số

Trâu: Mỗi bước có 2 khả năng và trong trường hợp tệ nhất là chia 2 và chia 3. Nên số lân chạy sẽ là \(O(\frac{(2k)!}{k!^2})\) với \(k = \lceil log_6(c) \rceil\)

Quy hoạch động: Nó sẽ không chạy lại những cái cần tính nên độ phức tạp thời gian là \(O(k^2 - 1)\) với \(k = log_6(c)\)

• Subtask 4: Trâu hoặc Quy hoạch động

Gọi \(f(x)\) là kết quả của bài toán với \(x = c\)

Trường hợp \(x = 1\) thì trả về \(1\)

Trường hợp \(x\) chia hết cho \(u\) thì tính kết quả của \(f(\frac{x}{u})\)

Trường hợp \(x\) chia hết cho \(o\) thì tính kết quả của \(f(\frac{x}{o})\)

Trường hợp \(x\) chia hết cho \(m\) thì tính kết quả của \(f(\frac{x}{m})\)

Trả về giá trị min của 3 giá trị trên hoặc trả về -1 khi không chia hết cho cả 3 số

Trâu: Mỗi bước có 3 khả năng và trong trường hợp tệ nhất là chia 2, chia 3 và chia 5. Nên số lân chạy sẽ là \(O(\frac{(3k)!}{k!^3})\) với \(k = \lceil log_{30}(c) \rceil\)

Quy hoạch động: Nó sẽ không chạy lại những cái cần tính nên độ phức tạp thời gian là \(O(k^3 - 1)\) với \(k = log_{30}(c)\)

\(\color{green}{\text{Code tham khảo }}\): Trâu

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(\frac{(2k)!}{k!^2})\ \color{purple}{\text{thời gian}}\ ||\ O(1)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>

using namespace std;

const int INF = 0x3f3f3f3f;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

long long c, u, o, m;
int magic(long long x = c)
{
    if (x == 1) return 0;

    int res = +INF;

    if (x % u == 0) minimize(res, magic(x / u) + 1);
    if (x % o == 0) minimize(res, magic(x / o) + 1);
    if (x % m == 0) minimize(res, magic(x / m) + 1);
    return res;
}

int query()
{
    cin >> c >> u >> o >> m;

    int res = magic();

    if (res == +INF) res = -1;
    cout << res << '\n';
    return 0;
}

int main()
{
    int q;
    cin >> q;

    while (q-->0)
    {
        query();



    }   

    return 0;
}

\(\color{green}{\text{Code tham khảo }}\): Tham lam

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(log_u(c) + log_o(c) + log_m(c))\ \color{purple}{\text{thời gian}}\ ||\ O(1)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>

using namespace std;

int query()
{
    long long c, u, o, m;
    cin >> c >> u >> o >> m;

    /// Make (u > o > m)
    if (u < o) swap(u, o);
    if (u < m) swap(u, m);
    if (o < m) swap(o, m);

    int cnt = 0;
    for (; c > 1 && c % u == 0; c /= u) ++cnt;
    for (; c > 1 && c % o == 0; c /= o) ++cnt;
    for (; c > 1 && c % m == 0; c /= m) ++cnt;

    if (c != 1) cnt = -1;
    cout << cnt << '\n';
    return 0;
}

int main()
{
    int q;
    cin >> q;

    while (q-->0)
    {
        query();



    }   

    return 0;
}

\(\color{green}{\text{Code tham khảo }}\): Quy hoạch động

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(log_{30}(n)^3 - 1)\ \color{purple}{\text{thời gian}}\ ||\ O(log_{30}(n)^3)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>
#include <unordered_map>

using namespace std;

const int INF = 0x3f3f3f3f;
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

long long c, u, o, m;
unordered_map<long long, int> f;

int magic(long long x = c)
{
    if (x == 1) return 0;

    if (f.count(x)) return f[x];
    int &res = f[x];
    res = +INF;

    if (x % u == 0) minimize(res, magic(x / u) + 1);
    if (x % o == 0) minimize(res, magic(x / o) + 1);
    if (x % m == 0) minimize(res, magic(x / m) + 1);
    return res;
}

int query()
{
    cin >> c >> u >> o >> m;

    f.clear();
    int res = magic();

    if (res == +INF) res = -1;
    cout << res << '\n';
    return 0;
}

int main()
{
    int q;
    cin >> q;

    while (q-->0)
    {
        query();



    }   

    return 0;
}