<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.95}}}}}\)
</button>

<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 trường hợp: } P = 1}\)

• \(\color{#903030}{\text{Mục tiêu:}}\) Tính xem số viên bi lấy được nhiều nhất sao cho không tồn tại cùng lúc 2 viên bi giống nhau (\(\frac{x}{y} \neq 1 \Leftrightarrow x \neq y\))

• \(\color{#903030}{\text{<Duyệt toàn tập>}}\)

Gọi \(A[]\) là dãy số nhận vào, \(A[] = \{a_1, a_2, \dots, a_n\}\)

Thử mọi dãy con \(S \subseteq A[]\) và kiểm tra nếu tồn tại \(i \neq j\) để \(S_i = S_j\) thì loại. Ngược lại trong số các tập con được chọn ta sẽ cập nhật kết quả tối ưu nhất: \(res = max\{|S|\}\)

Công thức: \(res = max\{|S|\}\) với \(S \subseteq A[], (\forall i \neq j \Leftrightarrow S_i \neq S_j)\)

• \(\color{#903030}{\text{<Sắp xếp và loại bỏ>}}\)

Ta sẽ sắp xếp mảng \(A[]\) tăng (giảm) dần.

Gọi tập \(S\) là tập kết quả. Cứ mỗi khi lấy một phần tử, ta loại tất cả các phần tử bằng nó, hoặc chặt nhị phân để nhảy tới vị trí đầu tiên có phần tử lớn (nhỏ) hơn tiếp theo.

Kết quả bài toán là \(res = |S|\)

• \(\color{#903030}{\text{<Cấu trúc dữ liệu>}}\)

Gọi CTDL \(S\) có thể tìm kiếm và chèn giá trị \(x\) vào tập.

Ta duyệt từng phần tử \(x \in A[]\). Nếu \(x \notin S\) thì ta chèn \(x\) vô \(S\).

Kết quả bài toán là \(res = |S|\)

• \(\color{#903030}{\text{<Độ phức tap>}}\)

\(\color{#903030}{\text{<Duyệt toàn tập>}}\) Có tất cả \(2^n\) tập con của \(A[] (n = |A|)\) \(\Rightarrow\) \(\Theta(2^n)\) thời gian

\(\color{#903030}{\text{<Sắp xếp và loại bỏ>}}\) Việc sắp xếp mất \(O(n\ log\ n)\) và loại bỏ mất \(O(n)\) \(\Rightarrow\) \(O(n\ log\ n)\) thời gian

\(\color{#903030}{\text{<Cấu trúc dữ liệu>::<Cây nhị phân tìm kiếm>}}\) Việc tìm kiếm và chèn mất \(O(log\ n)\) mỗi phần tử \(\Rightarrow\) \(O(n\ log\ n)\) thời gian

\(\color{#903030}{\text{<Cấu trúc dữ liệu>::<Mảng băm>}}\) Việc tìm kiếm và chèn mất \(O(1)\) mỗi phần tử \(\Rightarrow\) \(O(n)\) thời gian

\(\color{#009933}{\text{1. Code tham khảo}}\): <Cấu trúc dữ liệu>::<Mảng băm>

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

vector<ll> a;
int solve_p1()
{
    unordered_set<ll> S;
    for (ll x : a) S.insert(x);
    return S.size();
}

\(\color{#300000}{\text{2. Hướng dẫn trường hợp: } a_i \leq 20}\)

• \(\color{#7f5f3f}{\text{<Nhận xét tham lam>}}\) Nếu loại trường hợp \(P = 1\) riêng ra, thì khi ta lấy \(a_i\) thì mọi \(a_j = a_i\) ta cũng lấy vì \(\frac{a_i}{a_j} = 1 \neq P\)

• \(\color{#903030}{\text{Mục tiêu:}}\) Tính xem số viên bi lấy được nhiều nhất qua việc chọn các giá trị để lấy sao cho không tôn tại 2 giá trị bất kì chênh nhau \(P\) lần (\(\frac{x}{y} \neq P\ \forall x, y \in S\))

• \(\color{#903030}{\text{<Duyệt toàn tập>}}\)

Gọi tập các giá trị phân biệt trong \(A[]\) là \(T\)

Gọi \(f[x]\) là số lần \(x\) xuất hiện trong mảng \(A[]\)

Gọi giá trị của một tập \(S\) bất kì là \(V_S = \underset{x \in S}{\Sigma{f[x]}}\)

Ta sẽ thử từng tập \(S \subseteq T\) sao cho \(\forall x, y \in S\ \rightarrow x \neq P \times y\).

Kết quả bài toán sẽ là \(res = max(V_S)\)

• \(\color{#903030}{\text{<Quy hoạch động trạng thái>}}\)

Xét trạng thái hiện tại bằng một dãy bit bằng số nguyên \(mask\). Với việc không được chọn số \(x\) tương ứng bit thứ \(x\) của số \(mask\) được bật

Gọi \(g[mask]\) là giá trị tối đa khi không chọn các số được đánh dấu, ta sẽ xét 2 khả năng là chọn hoặc không chọn \(a[i]\), với khởi tạo là \(0\).

Kết quả bài toán là \(res = max(g[mask])\)

• \(\color{#903030}{\text{<Nhánh cận>}}\)

Gọi tập \(S\) là tập các giá trị không được chọn

Gọi đệ quy \(trau(S, i)\) là giá trị tói đa lấy được xét từ vị trí \([i] \rightarrow [n]\) và không chọn các giá trị \(x \in S\).

Kết quả bài toán là \(res = trau(\emptyset, 1)\)

• \(\color{#903030}{\text{<Độ phức tap>}}\) Nhìn chung thì đều vào khoảng \(O(2^{20})\)

\(\color{#903030}{\text{<Duyệt toàn tập>}}\) Chậm hơn vì phải xét tất cả trường hơn: \(O(f(x)) = O(2^{20})\)

\(\color{#903030}{\text{<Quy hoạch động trạng thái>}}\) Nhanh hơn nhưng tốn nhiều bộ nhớ không cần thiết. \(O(f(x)) \approx O(2^{20})\)

\(\color{#903030}{\text{<Nhánh cận>}}\) Nhanh hơn, tốt ít bộ nhớ và có thể giải lớn hơn \(O(f(x)) \leq O(2^k)\) với \(k\) là số phần tử phân biệt

\(\color{#c01515}{\text{2a. Tiếp cận quy hoạch động trạng thái}}\)

• \(\color{#f03030}{\text{<Mảng quy hoạch động>}}\) Gọi \(g[mask]\) là giá trị tối đa khi không chọn các số được đánh dấu. Số \(x\) được đánh dấu khi bit thứ \(x\) trong số nguyên \(mask\) được bật. Ban đầu \(g[mask] = 0\)

• \(\color{#f03030}{\text{<Công thức tính>}}\) Duyệt từng giá trị \(x \in \{1, 2, \dots, 20\}\).

Khi lấy \(x\), ta có \(g[mask] = g[mask | 2^{P \times x}] + f[x]\)

Khi bỏ qua \(x\), ta có \(g[mask] = g[mask | 2^{P \times x}]\)

Kết quả \(g[mask]\) sẽ là max của 2 cách chon.

Kết quả bài toán sẽ là \(res = max(g[mask])\)

Ta chỉ cần quan tâm các trạng thái trong khoảng \([0 \dots 2^{20} - 1]\), nếu ta gọi các trạng thái lớn hơn ta sẽ coi nó là \(0\).

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

• \(\color{#f03030}{\text{<Hàm đệ quy>}}\) \(trau(S, i)\) là giá trị tói đa lấy được xét từ vị trí \([i] \rightarrow [n]\) và không chọn các giá trị \(x \in S\)

Gọi \((v[i], f[i])\) là cặp (giá trị phân biệt \(v[i]\)) và (\(f[i]\) là số lần xuất hiện \(v[i]\) trong mảng \(A[]\))

• \(\color{#f03030}{\text{<Công thức tính>}}\)

Khi duyệt hết các mảng \(v[]\) thì \(trau(S, i) = 0\)

Nếu ta chọn \(a_i\)

Gọi \(x = P \times a_i\) là giá trị mình không được lấy khi lấy \(a_i\)

Nếu \(x \in A[]\) thì ta thêm vào tập \(S\)

Để tránh tràn số, ta khẳng định được ngay khi \(a[i] > \lfloor \underset{1..n}{max}(a[i])\ /\ P \rfloor\) thì \(x \notin A[]\)

Khi \(x \in A[]\) Ta có \(trau(S, i) = trau(S \cup x, i + 1) + f[a[i]]\)

Khi \(x \notin A[]\) Ta có \(trau(S, i) = trau(S, i + 1) + f[a[i]]\)

Nếu ta không chọn \(a[i]\), ta giữ nguyên tập \(S\). Nên ta có \(trau(S, i) = trau(S, i + 1)\)

\(\color{#009933}{\text{2a. Code tham khảo}}\): Quy hoạch động trạng thái

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

ll P;
const int lim = 20;
const int limmask = (1 << lim) - 1;

vector<int> f; /// f[x]    : So luong ai = x
vector<int> g; /// g[mask] : max so luong lay duoc & khong lay cac gia tri x co bit x duoc bat
int magic(int x = 1, int mask = 0)
{
    if (x > 20) return 0; /// Xet x trong doan [1..20]

    int &res = g[mask >> 1]; /// Bo qua bit thu [0]
    if (res != -1) return res;

    maximize(res, magic(x + 1, mask) + 0); /// Khong chon x
    if (mask >> x & 1) == false) /// Neu x chua duoc danh dau
    { 
        if (P * x <= 20) mask |= 1 << (P * x);    /// Chi quan tam cac gia tri < limmask
        maximize(res, magic(x + 1, mask) + f[x]); /// Chon x
    }

    return res;
}

int solve_p20()
{
    if (P == 1) return solve_p1();

    f.assign(lim, 0);
    for (ll x : a) ++f[x];

    g.assign(limmask + 1, -1);
    return magic();
}

\(\color{#009933}{\text{2b. Code tham khảo}}\): Nhánh cận

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

ll P;
ll lim;
int k; 
vector<ll> v;
vector<int> f;
int trau(set<ll> &S, int i = 0)
{
    if (i >= k) return 0;

    int res = 0;
    if (v[i] <= lim || S.count(v[i])) res = trau(S, i + 1); /// Neu khong chon v[i]
    if (S.count(v[i]) == false) /// Neu chon duoc v[i]
    {
        if (v[i] <= lim) /// Co the ton tai x
        {
            ll x = v[i] * P;
            bool marking = binary_search(all(v), x); /// mark = true <=> x thuoc A[]
            if (marking) S.insert(x);             
            maximize(res, f[i] + trau(S, i + 1));
            if (marking) S.erase(x);
        }
        else maximize(res, f[i] + trau(S, i + 1));
    }

    return res;
}

int solve_p20()
{
    if (P == 1) return solve_p1();
    ll mx = *max_element(all(a));
    lim = mx / P;

    map<ll, int> M;
    map<ll, int>::iterator it;
    for (int i = 0; i < n; ++i)
        ++M[a[i]];

    for (it = M.begin(); it != M.end(); ++it)
    {
        v.push_back(it -> first);  /// Cac gia tri v[i] phan biet
        f.push_back(it -> second); /// So lan xuat hien v[i] = trong A[]
    }

    k = v.size();
    return trau();
}

\(\color{#c01515}{\text{3. Hướng dẫn chia để trị}}\)

• \(\color{#7f5f3f}{\text{<Nhận xét chia>}}\) Nếu loại trường hợp \(P = 1\) ra, ứng với cách trên, có những giá trị sẽ không có liên quan và ảnh hưởng tới nhau. Ta sẽ chia dãy thành các nhóm để xử lí riêng. Trong đó giá trị \(x, y\) có thể ảnh hưởng nhau khi tồn tại số mũ \(k \in \mathbb{Z}\) để \(x = P^k \times y\).

• \(\color{#7f5f3f}{\text{<Nhận xét trị>}}\) Xét một bài toán con là tập con \(S \subseteq A[]\). Để tiện tính toán, hãy để dãy được sắp xếp giảm dần, và \(\exists x \in A[]\ \rightarrow\ \forall y \in S \{y = P^k\times x | k \in \mathbb{Z}\}\). Khi này, số lượng tối đa ta lấy được là việc chọn tối ưu các giá trị không kề nhau trong tập \(S\) (sau khi sắp xếp)

• \(\color{#f03030}{\text{<Phân tích độ phức tạp>}}\)

Khi \(P = 1\) thì \(O(n)\)

Lấy các cặp \((v_i, f_i)\) giảm dần: \(O(n\ \log\ n)\)

Phần chia: \(O(\Sigma(|S|)) = O(n)\)

Phần trị: \(O(|S|) = O(log_p(n))\)

Trường hợp chạy lâu nhất: Khi dãy phân biệt và có dạng \(x \times 2^k\), với \(x = 1..n\)

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

• \(\color{#f03030}{\text{<Xử lí chia>}}\) Gọi cặp \((v_i, f_i)\) nghĩa là giá trị \(v_i \in A[]\) xuất hiện đúng \(f_i\) lần. Và đặt \(F[v_i] = f_i\) và \(F[x \notin A[]] = 0\)

Ta sắp xếp mảng giảm dần theo \(v_i\). Duyệt theo thứ tự từ lớn xuống bé (để khỏi xét các giá trị \(\{x = v_i \times P^k\ |\ k \in \mathbb{N}^*\}\)

Ta sẽ chọn \(F[v_i], F[\frac{v_i}{P}], F[\frac{v_i}{P^2}], F[\frac{v_i}{P^3}], \dots\) vào tập mới để xử lí (chỉ chọn những kết quả \(F[v] \in \mathbb{N}\)). và loại các cặp được chọn ra

Lưu ý rằng nếu ta dùng phép nhân, hãy chú ý xử lí tràn số hoặc dùng phép tính bão hòa

• \(\color{#f03030}{\text{<Xử lí trị>}}\) Sau khi có tập \(S\) là số lượng xuất hiện của các giá trị dạng \(x = \frac{v_i}{P^k}\) sắp xếp giảm dần (theo \(x\)).

Ta sẽ dùng quy hoạch động xét \(magic(i)\) là giá trị tối đa khi xét từ \([i] \rightarrow [n]\)

Khi duyệt hết \((i = n + 1)\) có \(magic(i) = 0\)

Khi chọn \(S_i\), ta không được chọn \(S_{i + 1}\), nên \(magic(i) = magic(i + 2) + S_i\)

Khi không chọn \(S_i\), ta được chọn \(S_{i + 1}\), nên \(magic(i) = magic(i + 1) + 0\)

Kết quả của \(magic(i)\) là max của 2 cách trên

Kết quả của bài toán là \(res = magic(1)\)

\(\color{#009933}{\text{3a. Code tham khảo}}\): <Chia để trị>::Chia, <Cấu trúc dữ liệu>::Map

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

int n;
ll P;
vector<ll> a;
vector<ll> S;
vector<ll> f;
int main()
{
    cin >> n >> P;
    a.resize(n);
    for (ll &x : a) cin >> x;

    if (P == 1)
    {
        unordered_set<ll> S;
        for (ll x : a) S.insert(x);
        cout << S.size();
        return 0;
    }

    map<ll, int, greater<ll> > M;
    map<ll, int, greater<ll> >::iterator it;
    for (ll x : a) ++M[x];

    ll res = 0;
    for (it = M.begin(); it != M.end(); ++it)
    {
        ll  v = it -> first;
        int f = it -> second;
        S.assign(1, f);

        while (v % P == 0)
        {
            v /= P;
            if (M.count(v) == false) break; /// Co the bo nhanh can
            S.push_back(M[v]);
            M.erase(v);
        }

        f.assign(S.size(), -1);
        res += solve();
    }
    cout << res;
    return 0;
}

\(\color{#009933}{\text{3b. Code tham khảo}}\): <Chia để trị>::Trị, <Quy hoạch động>

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

vector<ll> S;
vector<ll> f;
ll solve(int i = 0)
{
    if (i >= S.size()) return 0LL;

    ll &res = f[i];
    if (res != -1) return res;
    maximize(res, solve(i + 1) + 0);    /// Khong chon S[i]
    maximize(res, solve(i + 2) + S[i]); ///   Co  chon S[i]

    return res;
}