Chia Hết (CHIAHET)

Nguồn: CLUE OJ Độ khó: Khá Số học Nguyên lý bù trừ Duyệt bitmask BCNN – UCLN

Đề bài

Giới hạn thời gian: 1 giây  ·  Giới hạn bộ nhớ: 524288 KB

Cho $m$ số nguyên dương $a_i$. Hỏi có bao nhiêu số nguyên dương chia hết cho ít nhất 1 số $a_i$ nào đó và không lớn hơn $n$.

Dữ liệu vào:

• Dòng thứ nhất chứa số nguyên $n$ và $m$ $(1 \le n \le 10^9,\ 1 \le m \le 15)$.
• Dòng tiếp theo là các số nguyên $a_i$ $(1 \le a_i \le 10^9)$.

Dữ liệu ra: Đáp án của bài toán là một số nguyên.

Ví dụ 1 – input

100 2
2 3

Ví dụ 1 – output

67

Ví dụ 2 – input

100 3
2 3 7

Ví dụ 2 – output

72

Lời mở đầu

Bài này nhìn đề ngắn gọn, đọc xong ai cũng nghĩ ngay ra cách làm, nhưng để qua được giới hạn $n \le 10^9$ thì phải "nặn óc" ra một chút với nguyên lý bao hàm – loại trừ (hay còn gọi là nguyên lý bù trừ) kết hợp với duyệt tập con bằng dãy nhị phân. Mình sẽ đi từ cách vét cạn dễ nhất rồi phân tích dần lên cách tối ưu, kèm khung chạy tay từng dòng để các bạn dễ theo dõi nhé 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Ở ví dụ 1, $n = 100$ và dãy là $\{2, 3\}$: ta cần đếm các số từ $1$ đến $100$ mà chia hết cho $2$ hoặc chia hết cho $3$ (chia hết cho cả hai cũng được, nhưng chỉ đếm 1 lần). Đó là các số $2, 3, 4, 6, 8, 9, 10, 12, \dots, 98, 99, 100$ – đếm ra có đúng $67$ số. Ví dụ 2 tương tự với dãy $\{2, 3, 7\}$, đếm được $72$ số.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Vét cạn từng số O(N·M) · TLECách 2Bao hàm – loại trừ + duyệt bitmask O(2^M·M)

Cách 1Vét cạn xét từng số – O(N·M)

Cách làm cơ bản nhất, dễ dàng nhìn ra đó chính là vét cạn xét tất cả mọi trường hợp. Cụ thể ta xét từng số $i$ trong đoạn từ $1$ đến $n$, với mỗi số ta kiểm tra xem nó có chia hết cho ít nhất 1 giá trị $a[j]$ nào đó không. Nếu có thì số $i$ hợp lệ, ta tăng biến đếm lên rồi break luôn (để không đếm một số nhiều lần). Sau cùng biến đếm chính là số lượng các số không vượt quá $n$ và chia hết cho ít nhất 1 giá trị $a[j]$ – đúng như đề bài cần.

Cách làm này luôn đảm bảo cho ra kết quả chính xác (tất nhiên phải cài đặt đúng nhé 😁) và rất dễ cài đặt.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    int a[m];
    for(int i = 0; i < m; ++i){
        cin >> a[i];
    }
    int cnt = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 0; j < m; ++j){
            if(i % a[j] == 0){
                cnt++;
                break;
            }
        }
    }
    cout << cnt;
    return 0;
}

n, m = map(int, input().split())
a = list(map(int, input().split()))
cnt = 0
for i in range(1, n + 1):
    for j in range(m):
        if i % a[j] == 0:
            cnt += 1
            break
print(cnt)

C++▶ Chạy tay từng dòng codeCách 1: xét từng số i từ 1 đến n, gặp a[j] chia hết thì đếm và break.

Dữ liệu vào (stdin) – sửa thoải mái20 2 2 3

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 int n, m;

6 cin >> n >> m;

7 int a[m];

8 for(int i = 0; i < m; ++i){

9 cin >> a[i];

10 }

11 int cnt = 0;

12 for(int i = 1; i <= n; ++i){

13 for(int j = 0; j < m; ++j){

14 if(i % a[j] == 0){

15 cnt++;

16 break;

17 }

18 }

19 }

20 cout << cnt;

21 return 0;

22}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(M)$ – chỉ có mảng $a$ gồm $M$ phần tử.
• Thời gian: hai vòng lặp lồng nhau, ngoài chạy $N$ lần, trong chạy tối đa $M$ lần ⇒ $O(N \cdot M)$.

Không gian$O(M)$

Thời gian$O(N \cdot M)$

Chắc chắn bị TLE

Với $O(N \cdot M)$, trường hợp xấu nhất $N = 10^9$, $M = 15$ thì cần tới $15 \cdot 10^9$ phép tính – vượt xa ngưỡng 1 giây (khoảng $(3 \div 5) \cdot 10^7$, cao lắm là $10^8$ phép tính). Tuy nhiên ta vẫn nên cài đặt nó để làm công cụ kiểm tra tính chính xác cho thuật toán tối ưu hơn mà ta sẽ làm ra sau đây.

Cách 2Bao hàm – loại trừ + duyệt tập con bằng bitmask – O(2^M·M)

Đếm bội số không cần vòng lặp

Cùng xem lại ví dụ 1 nhé: cho $n = 100$, hỏi có bao nhiêu số từ $1$ đến $n$ chia hết cho $2$? Đâu nhất thiết phải lặp từ $1$ đến $100$ rồi kiểm tra đúng không? Ta tính ngay được bằng phép chia nguyên $\lfloor 100 / 2 \rfloor = 50$ – có 50 số chia hết cho $2$. Tương tự có $\lfloor 100 / 3 \rfloor = 33$ số chia hết cho $3$.

Ý chính

Số lượng số trong đoạn $[1, n]$ chia hết cho $x$ là $\left\lfloor \dfrac{n}{x} \right\rfloor$ – tính trong $O(1)$.

Vậy tổng $50 + 33 = 83$ số chia hết cho $2$ hoặc $3$? Mà chờ đã, có gì sai sai? Đáp án đề đưa ra là $67$ cơ mà 🤔. Lúc này ta phải hiểu rằng đã có những số bị tính trùng: đó là những số vừa chia hết cho $2$, vừa chia hết cho $3$, như $6, 12, 18, 24, \dots$ Số nhỏ nhất vừa chia hết cho $2$ vừa chia hết cho $3$ chính là bội chung nhỏ nhất $\text{BCNN}(2, 3) = 6$, và các số còn lại cứ cộng lên $6$ đơn vị. Có $\lfloor 100 / 6 \rfloor = 16$ số như vậy, nên kết quả đúng là $83 - 16 = 67$ ✅.

Khi có nhiều hơn 2 số

Với 2 số thì dễ nhìn ra, nhưng đề cho tới 15 số thì sao? Mình phân tích qua ví dụ 2 với dãy $\{2, 3, 7\}$ để các bạn thấy rõ công thức tổng quát. Đầu tiên liệt kê các tập con của dãy:

• Tập con 1 phần tử: $\{2\}$, $\{3\}$, $\{7\}$.
• Tập con 2 phần tử: $\{2, 3\}$, $\{2, 7\}$, $\{3, 7\}$.
• Tập con 3 phần tử: $\{2, 3, 7\}$.

Bước 1 – cộng các tập 1 phần tử. Có $\lfloor 100/2 \rfloor = 50$ số chia hết cho $2$ ($2, 4, 6, \dots, 100$), $\lfloor 100/3 \rfloor = 33$ số chia hết cho $3$ ($3, 6, 9, \dots, 99$), $\lfloor 100/7 \rfloor = 14$ số chia hết cho $7$ ($7, 14, 21, \dots, 98$). Cộng lại $50 + 33 + 14 = 97$.

Bước 2 – trừ các tập 2 phần tử. Ở trên ta đã tính trùng những số chia hết cho cùng lúc 2 giá trị, nên phải loại ra:

• $\{2, 3\}$: BCNN $= 6$, có $\lfloor 100/6 \rfloor = 16$ số: $6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, 96$.
• $\{2, 7\}$: BCNN $= 14$, có $\lfloor 100/14 \rfloor = 7$ số: $14, 28, 42, 56, 70, 84, 98$.
• $\{3, 7\}$: BCNN $= 21$, có $\lfloor 100/21 \rfloor = 4$ số: $21, 42, 63, 84$.

Vậy $97 - 16 - 7 - 4 = 70$. Ủa vẫn chưa ra $72$? 😅

Bước 3 – cộng lại tập 3 phần tử. Để ý số $42$ và $84$ xuất hiện ở cả 3 danh sách loại ở bước 2. Ở bước 1 chúng được cộng 3 lần, bước 2 lại bị trừ 3 lần ⇒ thành ra không được đếm lần nào, hụt mất 2 số. Vậy ta cần cộng thêm các số chia hết cho cả $2, 3, 7$: BCNN $= 42$, $\lfloor 100/42 \rfloor = 2$ ⇒ $70 + 2 = 72$ 🎉 đúng với đáp án đề.

Hình dưới chia $72$ số đó theo từng "vùng" của biểu đồ Venn, các bạn cộng thử sẽ thấy $29 + 15 + 5 + 14 + 5 + 2 + 2 = 72$:

Vùng giữa (2 số: $42, 84$) bị cộng 3 lần, trừ 3 lần, nên phải cộng lại 1 lần nữa.

Công thức tổng quát (nguyên lý bao hàm – loại trừ)

Xét tất cả các tập con khác rỗng $S$ của dãy $a$. Với mỗi tập con tính $\text{BCNN}(S)$ rồi tính $\left\lfloor \dfrac{n}{\text{BCNN}(S)} \right\rfloor$:

• Nếu $S$ có số phần tử lẻ ⇒ cộng giá trị này vào đáp án.
• Nếu $S$ có số phần tử chẵn ⇒ trừ giá trị này khỏi đáp án.

Liệt kê tập con bằng dãy nhị phân

Còn việc làm sao liệt kê ra hết các tập con của dãy $m$ phần tử? Quy tắc rất dễ: với dãy có $m$ phần tử thì có $2^m$ dãy nhị phân độ dài $m$, ứng với các giá trị từ $0$ đến $2^m - 1$. Ta viết mỗi giá trị ra dạng nhị phân, vị trí nào là bit 1 thì phần tử tương ứng ở vị trí đó được chọn. Ví dụ với $\{2, 3, 7\}$, $2^3 = 8$ dãy nhị phân:

Giá trị	Dãy nhị phân (ứng với 2 3 7)	Tập con	BCNN	$\lfloor 100 / \text{BCNN} \rfloor$	Số phần tử	res
0	000	không chọn gì (bỏ qua)	–	–	–	0
1	001	{7}	7	14	1 (lẻ)	+14 = 14
2	010	{3}	3	33	1 (lẻ)	+33 = 47
3	011	{3, 7}	21	4	2 (chẵn)	−4 = 43
4	100	{2}	2	50	1 (lẻ)	+50 = 93
5	101	{2, 7}	14	7	2 (chẵn)	−7 = 86
6	110	{2, 3}	6	16	2 (chẵn)	−16 = 70
7	111	{2, 3, 7}	42	2	3 (lẻ)	+2 = 72

Hết tập con để xét, đáp án sau cùng là $72$. Đây cũng chính là thứ tự mà code bên dưới duyệt.

Minh hoạ: mỗi số được đếm bao nhiêu lần?

Để thấy rõ vì sao "lẻ thì cộng, chẵn thì trừ" lại đúng, khung dưới đây duyệt các tập con theo thứ tự 1 phần tử → 2 phần tử → 3 phần tử... Mỗi ô là một số từ $1$ đến $n$, con số nhỏ phía trên là số lần nó đang được đếm. Bấm Tiếp và để ý: đến bước cuối, mọi số chia hết cho ít nhất một $a_i$ đều được đếm đúng 1 lần, còn lại là 0 lần.

n dãy a

Ví dụ nhanh:

Nhập tối đa 6 số; dải ô chỉ vẽ khi n ≤ 120.

Tính BCNN và cái bẫy tràn số

Khi đã có tập con rồi thì đi tìm BCNN của tất cả phần tử trong tập con đó như thế nào? Đầu tiên ta lấy BCNN của $1$ với phần tử đầu tiên – lúc này BCNN chính là phần tử đầu tiên đó luôn. Rồi lấy kết quả đó tìm BCNN với phần tử tiếp theo, cứ thế đến cuối tập con. Tóm lại bản chất chỉ là tìm BCNN của lần lượt 2 số và lặp từ đầu đến cuối.

BCNN của 2 số

$\text{BCNN}(a, b) = \dfrac{a \cdot b}{\text{UCLN}(a, b)}$. Trong C++14 chưa có sẵn hàm lcm nhưng có __gcd, nên mình dùng công thức này. Bạn nào dùng C++17 trở lên thì có sẵn lcm trong thư viện <numeric>, xài tiện hơn.

Coi chừng tràn số

Các phần tử có thể lên tới $10^9$. Giả sử dãy toàn là số nguyên tố lớn gần $10^9$: UCLN của 2 số nguyên tố khác nhau luôn là $1$, nên BCNN của tập con chính là tích các phần tử – 15 số cỡ $10^9$ nhân với nhau thì đến long long (64 bit) cũng không chứa nổi.

Để tránh tình huống này, ngay từ đầu mình sắp xếp mảng $a$ tăng dần, như vậy các tập con lấy ra cũng có giá trị tăng dần, BCNN được tính từ số nhỏ đến số lớn. Và quan trọng nhất: ngay khi BCNN tính ra vượt quá $n$ thì dừng lại, không cần xét tiếp tập con đó nữa. Tại sao lại được như vậy? Vì BCNN chỉ có thể tiếp tục tăng chứ không giảm, mà đã lớn hơn $n$ thì $\lfloor n / \text{BCNN} \rfloor$ chắc chắn bằng $0$ (số nhỏ chia số lớn) – tập con này không đóng góp gì cả. Vừa kết thúc sớm cho nhanh, vừa tránh được tràn số.

Vì sao dừng sớm là đủ an toàn?

Trước mỗi lần nhân, mul luôn $\le n \le 10^9$ (nếu lớn hơn thì đã dừng rồi), còn $a[j] \le 10^9$, nên tích mul * a[j] tối đa $10^{18}$ – vừa vặn trong long long (giới hạn khoảng $9.2 \cdot 10^{18}$). Do đó các bạn nhớ khai báo mul và mảng $a$ là long long nhé.

Ở trên là mình đã mô tả rất kỹ ý tưởng rồi nhé. Các bạn nào chưa làm được thì thử tự cài đặt theo đúng ý tưởng trước, rồi hẵng xem code. Trong code, mảng b lưu dãy nhị phân của i: lấy temp % 2 rồi temp /= 2 liên tục, ghi từ cuối mảng ngược lên đầu, nên bit cuối cùng của i ứng với phần tử cuối của $a$ – đúng như bảng ở trên.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, m;
    cin >> n >> m;
    long long a[m];
    for(int i = 0; i < m; ++i){
        cin >> a[i];
    }
    sort(a, a + m);
    long long sum = 0;
    int b[m] = {0};
    int sz = (int)pow(2, m);
    for(int i = 1; i < sz; ++i){
        int j = m - 1;
        int temp = i;
        while(temp != 0){
            b[j--] = temp % 2;
            temp /= 2;
        }
        bool check = true;
        long long mul = 1;
        int cnt = 0;
        for(j++; j < m; j++){
            if(b[j] == 1){
                mul = (mul * a[j]) / __gcd(mul, a[j]);
                cnt++;
                if(mul > n){
                    check = false;
                    break;
                }
            }
        }
        if(check == true){
            if(cnt % 2 != 0){
                sum += n / mul;
            }
            else{
                sum -= n / mul;
            }
        }
    }
    cout << sum;
    return 0;
}

from math import gcd

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
# lcm[mask] = BCNN của tập con mask, nếu vượt n thì lưu n + 1 (coi như "quá n")
lcm = [1] * (1 << m)
total = 0
for mask in range(1, 1 << m):
    low = mask & (-mask)              # bit 1 thấp nhất của mask
    j = low.bit_length() - 1          # vị trí phần tử ứng với bit đó
    prev = lcm[mask ^ low]            # BCNN của tập con bỏ phần tử j
    if prev > n:
        cur = n + 1
    else:
        cur = prev * a[j] // gcd(prev, a[j])
        if cur > n:
            cur = n + 1
    lcm[mask] = cur
    if cur <= n:
        if bin(mask).count('1') % 2 != 0:
            total += n // cur
        else:
            total -= n // cur
print(total)

Về bản Python

Bản Python chép nguyên kiểu tách bit như C++ thì với $m = 15$ chạy khoảng 2–3 giây trên máy mình. Nên bản Python ở trên mình viết gọn hơn một chút nhưng vẫn cùng ý tưởng: BCNN của tập con mask được tính từ BCNN của tập con bỏ đi 1 phần tử (mask ^ low), mỗi tập con chỉ cần 1 lần tính UCLN; BCNN vượt $n$ thì lưu là $n + 1$ (coi như "quá n", đóng góp 0).

C++▶ Chạy tay từng dòng codeCách 2: duyệt i = 1 … 2^m − 1, tách bit ra mảng b, tính BCNN, lẻ cộng – chẵn trừ.

Dữ liệu vào (stdin) – sửa thoải mái100 3 2 3 7

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main() {

5 long long n, m;

6 cin >> n >> m;

7 long long a[m];

8 for(int i = 0; i < m; ++i){

9 cin >> a[i];

10 }

11 sort(a, a + m);

12 long long sum = 0;

13 int b[m] = {0};

14 int sz = (int)pow(2, m);

15 for(int i = 1; i < sz; ++i){

16 int j = m - 1;

17 int temp = i;

18 while(temp != 0){

19 b[j--] = temp % 2;

20 temp /= 2;

21 }

22 bool check = true;

23 long long mul = 1;

24 int cnt = 0;

25 for(j++; j < m; j++){

26 if(b[j] == 1){

27 mul = (mul * a[j]) / __gcd(mul, a[j]);

28 cnt++;

29 if(mul > n){

30 check = false;

31 break;

32 }

33 }

34 }

35 if(check == true){

36 if(cnt % 2 != 0){

37 sum += n / mul;

38 }

39 else{

40 sum -= n / mul;

41 }

42 }

43 }

44 cout << sum;

45 return 0;

46}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(2 \cdot M)$ – ngoài mảng $a$ đề cho, cần thêm mảng phụ $b$ lưu dãy bit nhị phân độ dài $M$, tức là $O(M)$.
• Thời gian:
  • Sắp xếp mảng $a$: $O(M \log M)$, mà $M \le 15$ nên không đáng kể.
  • Với mỗi tập con: tách bit và duyệt mảng $b$ ($M$ phần tử), mỗi phần tử được chọn thì tính UCLN mất $O(\log(\min(a, b)))$ – dù $a, b$ lên tới $10^9$ thì cũng chỉ vài chục bước.
  • Đáng kể nhất là xét từng tập con: có $2^M - 1$ tập con.
  Tổng cộng $O(M \log M) + O(2^M \cdot M \cdot \log(\max a))$, gọn lại là $O(2^M \cdot M)$. Với $M = 15$ thì $2^{15} = 32768$ tập con, cộng hết mấy râu ria lại cũng chỉ cỡ vài triệu phép tính.

Không gian$O(M)$

Thời gian$O(2^M \cdot M)$

Vậy từ $15 \cdot 10^9$ rút xuống còn cỡ vài triệu phép tính thì yên tâm không bị TLE. Các bạn đã thấy cái hay của giải thuật chưa: phải nặn óc ra suy nghĩ nhưng chương trình chạy nhanh hơn rất nhiều hehe 😎.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 500 bộ test ngẫu nhiên nhỏ ($n \le 3000$, $m \le 15$, $a_i$ đến $10^9$), so với code vét cạn – khớp hết, và đúng cả 2 ví dụ của đề. Với $n = 10^9$, $m = 15$: cách 2 (C++) chạy chưa tới 0.1 giây, bản Python khoảng 0.4–0.8 giây; còn cách 1 (C++) mất khoảng 140 giây ⇒ TLE đúng như phân tích.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇