1308 - Biểu diễn dãy số

Tóm tắt đề bài Tìm một dãy gồm $n$ số nguyên dương phân biệt không vượt quá $10^6$ , sao cho bội chung nhỏ nhất của dãy không vượt quá $10^6$ . Giới hạn: $n \leq 100$

Lời giải

Để tối ưu hóa số phần tử của dãy, ta sẽ chọn một số nguyên dương $x$ , và thêm tất cả các ước của $x$ vào dãy $a$ . Khi đó:
- Bội chung nhỏ nhất của dãy $a$ cũng chính là số nguyên $x$ .
- Số phần tử của dãy $a$ cũng chính là số ước của $x$ . Giả sử phân tích thừa số nguyên tố của $x$ là $x$ = $p_1^{r_1}p_2^{r_2} . . . p_k^{r_k}$ thì số ước của $x$ là $(r_1 + 1)(r_2 + 1) . . . (r_k + 1)$ .

Ta có thể chọn $x$ là tích của $7$ số nguyên tố nhỏ nhất $(x = 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 = 510510)$ .

Khi đó, số ước của $x$ là $(1 + 1)^7 = 128$ . Số ước này là đủ để ta thêm vào dãy $a$ .

Việc liệt kê các ước của $x$ bằng cách duyệt trâu là đủ nhanh với giới hạn đề bài đã cho. Tuy nhiên, ta có thể thực hiện nhanh hơn bằng cách làm sau:

Duyệt qua tất cả các mặt nạ bit mask có giá trị từ $0$ đến $n - 1$ , gồm 7 chữ số nhị phân.
Mỗi $mask$ sẽ tương ứng với một ước $d$ của $x$ , với bit thứ $i$ của $mask$ bằng $1$ khi và chỉ khi $d$ chia hết cho số nguyên tố nhỏ thứ $i$ . Ta sẽ tính giá trị $d$ dựa vào mask và thêm $d$ vào mảng $a$ .
Chẳng hạn, với $mask = 0100111_2$ thì $d = 2 \times 3 \times 5 \times 13$ .

Mã nguồn tham khảo:

#include <bits/stdc++.h>
using namespace std;
int prime[7] = {2, 3, 5, 7, 11, 13, 17};
int main() {
    int n;
    scanf("%d", &n);
    for(int mask = 1; mask <= n; ++mask) {
        int num = 1;
        for(int i = 0; i < 7; ++i)
            if ((mask>>i)&1)
                num *= prime[i];
        printf("%d ", num);
    }
    return 0;
}

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

Tìm hiểu thêm về các keyword cho bài toán này: constructive algorithm, number theory, bitmask