let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

C11HUM - Số khiêm tốn

solution.md

Xét ví dụ đề bài, dãy số khiêm tốn cho 4 só nguyên tố 2, 3, 5, 7 là:

2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120 125,...

Ta thấy các số chia hết cho 3 trong dãy trên là:

3 6 9 12 15 18 21 24 27 30 36 42 45 48 54 60 63 72 75 81 84 90 96 105 108 120

Thử chia dãy trên cho 3, ta được:

1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40

Ngoại trừ số 1 ở đầu ra thì dãy trên hoàn toàn giống với dãy số khiêm tốn ban đầu. Từ nhận xét này, ta có thể giải bài này bằng cách sau:

  • p[x] sẽ lần lượt lưu các số khiêm tốn chia hết cho x, ban đầu p[x] = x.
  • Ở mỗi lượt, ta chọn số khiêm tốn tiếp theo bằng cách tìm số nhỏ nhất trong p.
  • Gọi số vừa chọn được là z, ta cập nhật lại các p[x]p[x] == z. Việc cập nhật này sẽ tăng p[x] lên thành phần tử tiếp theo trong dãy số khiêm tốn chia hết cho x.

Độ phức tạp: O(NK).

main.cpp
Open in Github Download
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

struct pack {
    ll value;
    ll prime;
    int index;
};

bool operator < (const pack &a, const pack &b) {
    return a.value < b.value;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int k, n; cin >> k >> n;
    vector<pack> p(k);
    for (pack &p: p) {
        cin >> p.prime;
        p.value = p.prime;
        p.index = -1;
    }
    vector<ll> res;
    while (n--) {
        auto i = min_element(p.begin(), p.end());
        res.push_back(i->value);
        for (pack &p: p) if (p.value == res.back()) {
            p.value = p.prime * res[++p.index];
        }
    }
    cout << res.back();
    return 0;
}
Comments