I. Tổng quan về bit và xử lý bit

Chúng ta đều biết rằng máy tính làm việc với các giá trị nhị phân $0 - 1,$ gọi là các bit, nhờ vậy máy tính hoạt động vô cùng nhanh. Trong lập trình thi đấu, việc áp dụng các bit nhị phân để xử lý bài toán là một kĩ thuật cực kì thú vị, không chỉ giúp cho tốc độ thuật toán được cải thiện đáng kể, mà còn làm tối ưu bộ nhớ và đơn giản hóa chương trình. Kĩ thuật này được gọi là Thao tác bit (Bit Manipulation), là kĩ thuật sử dụng các bit của một số nguyên không âm (biểu diễn nhị phân) để biểu diễn một tập hợp, đi kèm với đó là những mẹo để xử lý các bit của một số nguyên.

Trong chuyên đề này, chúng ta sẽ cùng thảo luận về ứng dụng của Thao tác bit trong Lập trình thi đấu và phân tích một số bài tập cụ thể liên quan tới kĩ thuật này. Nhưng trước tiên hãy cùng nhắc lại những kiến thức cơ bản liên quan tới bit!

1. Các toán tử trên bit (Bitwise operators)

Cơ bản

Những thứ cơ bản nhất (cũng là quan trọng nhất) trong thao tác bit là các toán tử trên bit - mà có lẽ ai học lập trình cũng đã từng nghe qua: AND (&), OR (|), XOR (^), NOT (~). Những toán tử này phần nào giống với các toán tử logic &&, || và !, tuy nhiên điều khác biệt là chúng sẽ làm việc trên các bit của hai số nguyên. Bảng chân trị của các toán tử này như sau:

Như vậy, khi sử dụng các toán tử này với hai số nguyên, chẳng hạn như 10 & 5, thì từng cặp bit tương ứng trên biểu diễn nhị phân của hai toán hạng sẽ được so khớp với nhau theo toán tử. Nếu như số lượng bit của hai số khác nhau, thì các chữ số $0$ sẽ được tự động thêm vào phía bên trái để độ dài biểu diễn nhị phân của chúng bằng nhau (số lượng chữ số $0$ thêm vào phụ thuộc vào kiểu dữ liệu của các số nguyên đó là bao nhiêu bit):

10 = 1010
5 = 0101
10 & 5 = 0000
10 | 5 = 1111
10 ^ 5 = 1111
~A = 0101
~B = 1010

Có hai toán tử thao tác bit nữa là NAND và NOR, tuy nhiên không có nhiều tác dụng trong lập trình thi đấu, vì vậy tôi sẽ không đề cập ở đây.

Toán tử dịch bit

Hai toán tử rất thường xuyên sử dụng mà ta cần nắm vững ở đây là dịch trái << và dịch phải >>. Nếu ta viết a << b thì ta đang dịch các bit của $a$ sang trái $b$ vị trí, còn nếu viết a >> b thì ta đang dịch các bit của $a$ sang phải $b$ vị trí. Đối với các số nguyên không âm, thì khi dịch trái, các bit mới có thể sẽ xuất hiện bên tay phải của số, chúng sẽ bằng $0$. Còn khi dịch phải, thì các bit bị dịch sang phải sẽ biến mất, các bit trống bên tay trái sẽ trở thành $0$. Ví dụ dưới đây giả định rằng các số nguyên được biểu diễn dưới dạng $8$ bit, và tác dụng của các phép dịch trái - dịch phải sẽ như sau:

10 << 2 = 00001010 << 2 = 00101000
10 >> 2 = 00001010 >> 2 = 00000010

Phép dịch trái $b$ bit tương ứng với việc nhân với $2^b,$ còn phép dịch phải $b$ bit tương ứng với việc chia nguyên cho $2^b$. Hai toán tử này thường xuyên được sử dụng để truy cập vào một bit bất kì của số nguyên - kĩ thuật mà ta sẽ bàn tới ở ngay phía sau.

Lưu ý: Khi tính toán các giá trị a << b mà có khả năng kết quả vượt quá int, các bạn phải tiến hành ép kiểu để tránh bị tràn số. Chẳng hạn như 1 << n là tính $2^n,$ khi $n \ge 32$ thì giá trị sẽ vượt quá int, vì thế ta phải viết là 1LL << n.

Độ ưu tiên của các toán tử thao tác bit

Bảng dưới đây thể hiện độ ưu tiên của tất cả các loại toán tử trong C++, theo quy tắc các nhóm toán tử có độ ưu tiên cao hơn sẽ ở hàng phía trên của bảng, và các toán tử trong cùng một nhóm sẽ có độ ưu tiên theo quy tắc từ trái sang phải hoặc từ phải sang trái:

Nhìn vào đây, ta có thể thấy các toán tử dịch bit << và >> có độ ưu tiên cao nhất trong các toán tử thao tác bit, tuy nhiên vẫn thấp hơn các phép toán số học +, -, *, / và %. Các phép toán gán có sự xuất hiện của thao tác bit cũng sẽ có độ ưu tiên thấp hơn các phép toán gán với toán tử số học. Các bạn cần chú ý điểm này để tránh nhầm lẫn khi tính toán.

2. Sử dụng bit để biểu diễn tập hợp

Biểu diễn tập hợp thông qua biểu diễn nhị phân

Ta có thể lợi dụng biểu diễn nhị phân của một số nguyên lên tới $32$ bit (hoặc $64$ bit nếu như ngôn ngữ lập trình của các bạn có kiểu số nguyên $64$ bit) để biểu diễn một tập hợp, với bit $1$ thể hiện rằng phần tử ở vị trí tương ứng có xuất hiện trong tập hợp, và bit $0$ để thể hiện phần tử đó không xuất hiện.

Giả sử $A$ và $B$ là hai biểu diễn nhị phân đại diện cho hai tập hợp, thì ta có thể sử dụng các toán tử thao tác bit để thực hiện các phép toán trên hai tập hợp này như sau:

• Phép toán hợp (Set union): A | B.
• Phép toán giao (Set intersaction): A & B.
• Phép toán hiệu (Set subtraction): A & ~B.
• Phép toán phủ định tập hợp (Set negation): ALL_BITS ^ A - với ALL_BITS là một số nguyên gồm toàn bit $1$ với độ dài bằng với độ dài của $A$.

"Bật" và "tắt" bit

Ta có thể "bật" (set) một bit ở vị trí $n$ của số nguyên $A$ lên với hai bước sau:

• Bước $1$: Tạo số nguyên với bit $1$ ở vị trí thứ $n,$ các bit còn lại đều bằng $0$ là 1 << n.
• Bước $2$: Lấy số nguyên $A$ đem OR với 1 << n. Vậy ta có công thức A |= (1 << n).

Hoàn toàn tương tự, ta có thể "tắt" (clear/unset) một bit ở vị trí $n$ của số nguyên $A$ với hai bước sau:

• Bước $1$: Tạo số nguyên với bit $1$ ở vị trí thứ $n,$ các bit còn lại đều bằng $0,$ rồi phủ định nó bằng toán tử NOT: ~(1 << n).
• Bước $2$: Lấy số nguyên $A$ đem AND với ~(1 << n). Vậy ta có công thức A &= (~(1 << n)).

Kiểm tra bit đang bật hay tắt

Ta có thể kiểm tra một bit ở vị trí $n$ của số $A$ có phải bằng $1$ không thông qua các bước sau:

• Bước $1$: Tạo số với bit $1$ ở vị trí $n$ bằng công thức 1 << n.
• Bước $2$: Lấy số $A$ đem AND với số 1 << n, nếu như bit ở vị trí $n$ đang bật thì kết quả sẽ khác $0,$ ngược lại thì kết quả sẽ bằng $0$. Vậy ta có công thức: A & (1 << n) != 0.

Lật bit

Lật bit là thao tác đảo ngược giá trị của bit, từ $0$ thành $1$ hoặc từ $1$ thành $0$. Lợi dụng toán tử XOR, ta có thể đảo bit ở vị trí $n$ của số $A$ như sau:

• Bước $1$: Tạo số với bit $1$ ở vị trí $n$ bằng công thức 1 << n.
• Bước $2$: Lấy số $A$ đem XOR với số 1 << n để thu được số mới đã lật bit tại vị trí $n$: A ^= (1 << n).

II. Một số mẹo hay với thao tác bit

Dựa vào bit, chúng ta có thể thực hiện rất nhiều các kĩ thuật với độ tối ưu cao. Trong phần này chúng ta sẽ cùng thảo luận về những kĩ thuật này. Nếu như áp dụng đúng cách, chúng sẽ giúp cho chương trình có tốc độ thực thi rất nhanh và có thể biến code của các bạn từ TLE thành AC ở những kì thi online.

1. Một số hàm builtin quan trọng trong thư viện GCC

Thư viện GCC cung cấp các hàm builtin (là các hàm không cần phải khai báo thư viện nào mà vẫn có thể sử dụng được) rất thú vị, mà có thể sẽ giúp ích trong quá trình giải quyết các bài toán liên quan tới xử lý bit. Dưới đây người viết xin liệt kê nhanh một vài hàm trong số đó:

Hàm __builtin_popcount(x)

Hàm này có tác dụng đếm số lượng bit $1$ trong biểu diễn nhị phân của số $x$.

Độ phức tạp: $O(\log_2 x)$.

Ví dụ

#include <iostream>

using namespace std;

main()
{
    int n = 5;
    cout << "Count of 1s in binary of " << n << " is " << __builtin_popcount(n);
	
    return 0;
}

Output

Count of 1s in binary of 5 is 2 

Hàm __builtin_parity(x)

Hàm này dùng để kiểm tra số lượng bit $1$ của số $x$ là lẻ hay chẵn. Hàm sẽ trả về $\text{TRUE} \ (1)$ nếu như số lượng bit $1$ của $x$ là lẻ, ngược lại trả về $\text{FALSE} \ (0)$

Độ phức tạp: $O(\log_2 x)$.

Ví dụ

#include <iostream>

using namespace std;

main()
{
    int n = 7; // 7 = 0111.
    cout << __builtin_parity(n);
	
    return 0;
}

Output

1

Hàm __builtin_clz(x)

Hàm này dùng để đếm số lượng bit $0$ liên tiếp đứng trước bit $1$ đầu tiên của số $x$ tính từ trái qua phải. Lưu ý, số lượng bit $0$ sẽ phụ thuộc vào kiểu dữ liệu của số $x,$ ví dụ số kiểu int sẽ có dạng $32$ bit, kiểu long long sẽ có dạng $64$ bit.

Lưu ý rằng, hàm này chỉ có thể sử dụng với các số nguyên không dấu có kiểu int. Các bạn có thể sử dụng hàm __builtin_clzl() cho kiểu dữ liệu long và __builtin_clzll() cho kiểu dữ liệu long long theo cách hoàn toàn tương tự. Ngoài ra, nếu tham số đầu vào của hai hàm này là $0$ thì giá trị trả về sẽ là undefined.

Độ phức tạp: $O(\log_2 x)$.

Ví dụ

#include <iostream>

using namespace std;

main()
{
    int n = 16; // 16 = 00000000 00000000 00000000 00010000.
    cout << "Count of leading zeros before the first bit 1 of " << n << " is " << __builtin_clz(n);
	
    return 0;
}

Output

Count of leading zeros before the first bit 1 of 16 is 27

Hàm __builtin_ctz(x)

Ngược lại với hàm __builtin_clz(), hàm này sử dụng để đếm số lượng bit $0$ liên tiếp đứng sau bit $1$ cuối cùng của số $x,$ theo chiều từ phải qua trái. Hoàn toàn tương tự ta có các hàm __builtin_ctzl() và __builtin_ctzll() dành cho các kiểu dữ liệu long và long long.

Lưu ý đặc biệt cho hàm này vẫn giống như hàm __builtin_clz() - sẽ trả về undefined nếu như tham số đầu vào bằng $0,$ ngoài ra không hoạt động với số nguyên có dấu.

Độ phức tạp: $O(\log_2 x)$.

Ví dụ

#include <iostream>

using namespace std;

main()
{
    int n = 16; // 16 = 00000000 00000000 00000000 00010000.
    cout << "Count of trailing zeros after the last bit 1 of " << n << " is " << __builtin_clz(n);
	
    return 0;
}

Output

Count of trailing zeros after the last bit 1 of 16 is 4

2. Các kĩ thuật thú vị với thao tác bit

Áp dụng các thao tác xử lý bit, ta có thể thực hiện được khá nhiều trick thú vị và đẩy nhanh được tốc độ thuật toán, tuy nhiên không phải trick nào cũng có ứng dụng thực tế (đôi khi chỉ để chém gió cho vui). Người viết sẽ liệt kê ra một số trick hay dưới đây, bạn đọc có thể tùy ý lựa chọn sử dụng trong các bài tập cụ thể nếu cảm thấy có tác dụng!

2.1. Kiểm tra một số bất kì có phải lũy thừa của 2 không?

Xét một số nguyên không âm $n,$ nếu như nó là lũy thừa của $2$ thì giá trị AND của $n$ và $n - 1$ sẽ bằng $0$. Tuy nhiên, công thức này không hoạt động nếu như $n = 0,$ vì thế các bạn cần kiểm tra thêm cả điều kiện $n \ne 0$.

bool is_power2(int n)
{
    return n != 0 && (!(n & (n - 1)));
}

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

2.2. Đếm số lượng số $x$ nhỏ hơn hoặc bằng $n$ thỏa mãn $n + x = n^x$

Số lượng giá trị $x$ nói trên có thể đếm nhanh bằng một công thức:

$$res = 2^m$$

Chú ý rằng, giá trị $m$ này được đếm dựa theo việc biểu diễn $n$ ở hệ nhị phân và loại bỏ đi các bit $0$ vô nghĩa ở phía tay phải.

int count_values(int n)
{
    int zero_bits = 0;
    while (n)
    {
        // Nếu n chẵn thì sẽ thu được một bit 0.
        // Công thức (n & 1) == 0 sẽ kiểm tra n có phải số chẵn không.
        zero_bits += ((n & 1) == 0);
        n >>= 1;
    }
	
    return 1 << zero_bits;
}

Độ phức tạp: $\approx O(1)$.

2.3. Duyệt mọi tập con của tập hợp

Với một tập hợp $A$ gồm $n$ phần tử, áp dụng thao tác bit chúng ta có thể nhanh chóng duyệt qua mọi tập con của nó (tốc độ thuật toán sẽ nhanh hơn đáng kể so với việc sử dụng quay lui với các lời gọi đệ quy). Ta sẽ sử dụng một dãy bit gồm $n$ phần tử đại diện cho các trạng thái lựa chọn của tập hợp $A,$ thì giá trị thập phân của các dãy bit đó sẽ nằm trong đoạn $[0, 2^n - 1]$. Khi đó, ta sẽ duyệt qua mọi số nguyên từ $0$ tới $2^n - 1$ và sử dụng mỗi số nguyên đó đại diện cho một cách lựa chọn tập con.

Khung thuật toán có thể mô tả sơ lược như sau

vector < int > a(n); // Tập hợp A gồm n phần tử.

// Xét tất cả các trạng thái tập con.
for (int mask = 0; mask < (1 << n); ++mask)
{
    // Xét từng phần tử của tập xem phần tử nào được chọn.
    // Phần tử i được chọn thì mask & (1 << i) = 1.
    for (int i = 0; i < n; ++i)
        if (mask & (1 << i))
        {
            // Ghi nhận phần tử a[i] vào tập con hiện tại.
            // Xử lý tùy ý tiếp theo.
        }
}

Với cách làm này, nếu như $B$ là tập con của $A$ thì số nguyên đại diện cho $B$ cũng sẽ luôn nhỏ hơn số nguyên đại diện cho $A,$ rất thuận lợi cho việc kết hợp với quy hoạch động. Kĩ thuật này cũng là kĩ thuật được sử dụng khá thường xuyên trong các bài toán áp dụng Duyệt phân đôi tập hợp (Meet in the middle), hoặc trong các bài toán về bao hàm - loại trừ. Chúng ta sẽ phân tích kĩ hơn về nó ở phần bài tập minh họa phía sau.

3. Sử dụng bitset trong C++

Trong STL C++ có một cấu trúc dữ liệu biểu diễn tập hợp các bit, có thể được sử dụng để hỗ trợ các thao tác xử lý bit rất tốt, đó là bitset.

Về bản chất, bitset giống như một mảng/vector kiểu logic, tức là nó gồm các phần tử chỉ mang giá trị $0 - 1,$ tuy nhiên nó được cài đặt một cách tối ưu sao cho mỗi phần tử chỉ chiếm đúng một bit. Vì thế, không gian lưu trữ của một bitset sẽ nhỏ hơn so với một mảng/vector kiểu bool. Các thao tác trên bitset cũng nhanh hơn so với mảng/vector tới $64$ lần.

Khai báo bitset

Để khai báo một bitset, ta sử dụng thư viện <bitset> và khai báo theo cú pháp dưới đây:

#include <bitset>

using namespace std;

bitset < size > {name}(intialization);

Trong đó:

• Tham số size thể hiện kích thước của bitset, tham số này bắt buộc phải có khi khai báo một bitset. Đây cũng là nhược điểm của bitset - kích thước phải cố định trước.
• Tham số name thể hiện tên của bitset.
• Tham số intialization thể hiện khởi tạo giá trị ban đầu của bitset. Có 3 cách để khởi tạo:

  • Không khởi tạo: Với cách này, bitset sẽ mặc định toàn bit $0$.

    bitset < 8 > unintialized_bitset; // 00000000.
    

  • Khởi tạo bằng số nguyên hệ thập phân: Với cách làm này, bitset sẽ được khởi tạo bằng với biểu diễn nhị phân của số truyền vào.

    bitset < 8 > decimal_bitset(15); // 00001111	
    

  • Khởi tạo bằng xâu nhị phân: Với cách làm này, bitset sẽ được khởi tạo giá trị bằng với xâu nhị phân truyền vào. Tuy nhiên, xâu truyền vào không được phép có độ dài lớn hơn kích thước của bitset.

    bitset < 8 > string_bitset(string("1111")); // 00001111.
    // Hoặc bitset < 8 > string_bitset("1111");
    

Truy cập các bit của bitset

Container bitset là một cấu trúc dữ liệu rất đặc biệt, nó vừa giống xâu kí tự lại vừa giống mảng. Giống xâu ở chỗ, nó có thể được khởi tạo từ một xâu nhị phân, và in ra cả dãy bit trực tiếp thông qua câu lệnh cout (chứ không cần for qua từng phần tử rồi in), nhưng lại giống mảng ở chỗ cũng truy cập được vào từng phần tử thông qua toán tử []. Tuy nhiên, các bit trong bitset lại được đánh số thứ tự từ phải qua trái (giống với quy tắc đánh số bit trong hệ nhị phân), bắt đầu từ $0$.

Cùng xem ví dụ dưới đây:

#include <iostream>
#include <bitset>

using namespace std;

main()
{
    bitset < 8 > sample_bitset("00001111");
    cout << "Bit at position 4 of sample_bitset is " << sample_bitset[4];
	
    return 0;
}

Kết quả đoạn code trên sẽ là

Bit at position 4 of sample_bitset is 0

Một số hàm thành viên của bitset

Container bitset có sẵn một số hàm thành viên, với tác dụng cụ thể như bảng dưới đây:

Cùng xem ví dụ dưới đây để hiểu cách hoạt động của các hàm trên:

#include <bitset>
#include <iostream>

using namespace std;

int main()
{
    // Declaring index variable.
    int index = 0;

    // Declaring a few bitset objects.
    bitset < 4 > all_set("1111"), all_unset;

    cout << "any() value: " << boolalpha << allSet.any() << endl;
    
    cout << "all() value: " << all_set.all() << endl;
    
    cout << "none() value: " << all_set.none() << endl;
    
    cout << "test() at index 0: " << noboolalpha << all_set.test(index) << endl;
    
    cout << "size() value: " << all_set.size() << endl;
    
    cout << "Value of all_unset on before using set(): " << all_unset << endl;
	
    all_unset.set(index);
    cout << "Value of all_unset on after using set(): " << all_unset << endl;

    cout << "Value of all_set on before using reset(): " << all_set << endl;
	
    all_set.reset(index);
    cout << "Value of all_set on after using reset(): " << all_set << endl;

    // Declaring an empty string.
    string bitString;
    // using to_string() method to assing value to empty string
    bit_string = all_set.to_string();
    cout << "bit_string: " << bit_string << endl;

    cout << "Unsigned Long value: " << all_set.to_ulong();

    return 0;
}

Kết quả chương trình trên sẽ là:

any() value: true
all() value: true
none() value: false
test() at index 0: 1
size() value: 4
Value of all_unset on before using set(): 0000
Value of all_unset on after using set(): 0001
Value of all_set on before using reset(): 1111
Value of all_set on after using reset(): 1110
bit_string: 1110
Unsigned Long value: 14

Các toán tử với bitset

Vì là một cấu trúc dữ liệu đặc trưng cho các bit nhị phân, nên các toán tử bitwise trong C++ được nạp chồng cho cả bitset. Như vậy, tất cả các toán tử &, |, !, <<=, >>=, &=, |=, ^=, ~ đều có thể sử dụng được trên bitset với ý nghĩa giống hệt như khi thao tác với kiểu số. Cùng xem ví dụ dưới đây:

// C++ program to show the different operator functions on
// bitset
#include <bitset>
#include <iostream>

using namespace std;

int main()
{
    bitset < 4 > bitset1("1001"), bitset2("1010");
    bitset < 4 > result;

    cout << "bitset1: " << bitset1 << "\nbitset2: " << bitset2 << endl;

    cout << "Accessing bit value at index 1 of bitset1: " << bitset1[1] << endl;

    // Bitwise AND.
    cout << "Bitwise AND using &: " << (result = bitset1 & bitset2) << endl;
    cout << "Bitwise AND using &=: " << (bitset1 &= bitset2) << endl;

    // Bitwise OR.
    bitset1 = 9; // 9 = 1001.
    cout << "Bitwise OR using &: " << (result = bitset1 | bitset2) << endl;
    cout << "Bitwise OR using &=: " << (bitset1 |= bitset2) << endl;

	// Bitwise NOT.
    cout << "Bitwise NOT: " << (result = ~bitset1) << endl;

    // Bitwise XOR.
    bitset1 = 9;
    cout << "Bitwise XOR: " << (bitset1 ^= bitset2) << endl;

    bitset1 = 9;
    cout << "Binary leftshift on bitwise1: " << (bitset1 <<= 1) << endl;
	
    bitset1 = 9;
    cout << "Binary rightshift on bitwise1: " << (bitset1 >>= 1) << endl;

    return 0;
}

Kết quả đoạn chương trình trên như sau:

Bitset1: 1001
Bitset2: 1010
Accessing bit value at index 1 of bitset1: 0
Bitwise AND using &: 1000
Bitwise AND using &=: 1000
Bitwise OR using &: 1011
Bitwise OR using &=: 1011
Bitwise NOT: 0100
Bitwise XOR: 0011
Binary leftshift on bitwise1: 0010
Binary rightshift on bitwise1: 0100

III. Bài tập minh họa

1. Nguyên tố cùng nhau

Đề bài

Cho trước một số nguyên dương $n$. Ta đã biết phi hàm Euler của $n,$ kí hiệu là $\phi(n)$ là số lượng số nguyên tố cùng nhau với $n$ và không vượt quá $n$. Sau khi nghiên cứu được khái niệm này, An tỏ ra rất hứng thú và đã dễ dàng viết xong chương trình tính phi hàm Euler của $n$. Tuy nhiên, không phải lúc nào chúng ta cũng cần xem xét trên cả đoạn số $[1, n],$ vì vậy An tự hỏi không biết có cách nào đếm số lượng số nguyên tố cùng nhau với $n$ trên đoạn $[1, m]$ hay không?

Yêu cầu: Cho trước hai số nguyên $n$ và $m,$ hãy đếm số lượng số nguyên tố cùng nhau với $n$ trên đoạn $[1, M]?$

Input:

• Một dòng duy nhất chứa hai số nguyên dương $n$ và $m$.

Ràng buộc:

• $1 \le m \le n \le{10}^{12}$.

Output:

• Số nguyên duy nhất là kết quả bài toán.

Sample Input 1:

10 5

Sample Output 1:

2

Ý tưởng

Để đếm số phần tử nguyên tố cùng nhau với $n$ từ $1$ tới $r,$ ta có thể đếm phần bù: Lấy $r$ trừ đi số phần tử KHÔNG nguyên tố cùng nhau với $n$ từ $1$ tới $r$. Giả sử $n$ phân tích ra thừa số nguyên tố là: $N = p_1^{k_1} \times p_2^{k_2} \times \cdots \times p_n^{k_n},$ thì các số KHÔNG nguyên tố cùng nhau với $N$ phải chia hết cho ít nhất một thừa số nguyên tố $p_i$ nào đó. Ta sẽ đếm số lượng này bằng cách xét các số chia hết cho $p_i$ trong đoạn $[1, r]$ bằng công thức $\left\lfloor{\frac{r}{p_i}} \right\rfloor$. Tuy nhiên, nếu chỉ đếm mỗi số lượng này thì sẽ bị thừa rất nhiều số, do có những số chia hết cho $2$ số $p_i,$ cho $3$ số $p_i...$Vì vậy ta áp dụng công thức bao hàm - loại trừ ở đây để tính. Công thức là:

$$\text{(Các số chia hết cho } 1 \text{ số } p_i) - \text{(Các số chia hết cho } 2 \text{ số } p_i) + \text{(Các số chia hết cho } 3 \text{ số } p_i) - \cdots +$$

Để sinh nhanh được các tập con của dãy số nguyên tố $p,$ ta sử dụng kĩ thuật xử lý bit như đã đề cập ở mục II. Với mỗi tập con ta tính tích của chúng để tạo thành bội chung nhỏ nhất của số chia hết cho $1, 2, 3,...$ số nguyên tố trong tập $p$.

Độ phức tạp: $O(\sqrt{n}),$ thời gian chạy chủ yếu lâu ở bước phân tích thừa số nguyên tố.

Code mẫu

#include <bits/stdc++.h>
#define int long long

using namespace std;

int N, M;

void enter()
{
    cin >> N >> M;
}

vector < int > extract(int N)
{
    vector < int > p;
    for (int i = 2; i * i <= N; ++i)
        if (N % i == 0)
        {
            p.push_back(i);

            while (N % i == 0)
                N /= i;
        }

    if (N > 1)
        p.push_back(N);

    return p;
}

void solution(int N, int M)
{
    vector < int > prime = extract(N);
    int K = prime.size();

    int inverse_path = 0; // Tính phần bù: Số lượng phần tử KHÔNG nguyên tố cùng nhau với N từ 1 tới r.
    for (int bitmask = 0; bitmask < (1 << K); ++bitmask) // Duyệt các trạng thái chọn tập con của tập hợp prime.
    {
        int group_count = 0, multi = 1; // Đếm số phần tử được chọn và tích các phần tử được chọn.
        for (int i = 0; i < K; ++i)
            if (bitmask & (1 << i)) // Phần tử i được chọn trong trạng thái hiện tại.
            {
                ++group_count;
                multi *= prime[i];
            }

        int cur_divisors = M / multi; // Số lượng số chia hết cho nhóm được chọn từ 1 tới r.
        if (group_count & 1) // Nếu nhóm này có số lượng lẻ -> bước cộng.
            inverse_path += cur_divisors;
        else // Nếu nhóm này có số lượng chẵn -> bước trừ.
            inverse_path -= cur_divisors;
    }

    cout << M - inverse_path; // Kết quả là r trừ đi phần bù.
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    enter();
    solution(N, M);

    return 0;
}

2. Sum Set

Đề bài

Cho dãy $a$ gồm $n$ phần tử nguyên dương.

Yêu cầu: Hãy đếm số tổng khác nhau có thể tạo ra từ các dãy con không nhất thiết liên tiếp của $a$ (không tính dãy rỗng)?

Input:

• Dòng thứ nhất chứa số nguyên dương $n$ miêu tả số phần tử trong dãy.
• Dòng thứ hai gồm $n$ phần tử miêu tả dãy $a$.

Ràng buộc:

• $1 \le n \le 1000$
• $0 < a_i \le 1000; \forall i: 1 \le i \le n$.

Subtasks:

• Subtask $1$ ($30\%$ số điểm): $n \le 20$.
• Subtask $2$ ($40\%$ số điểm): $n \le 50$.
• Subtask $3$ ($30\%$ số điểm): Không có ràng buộc gì thêm.

Output:

• Gồm một số nguyên dương là kết quả bài toán.

Sample Input:

3
1 4 5

Sample Output:

6

Ý tưởng

Subtask 1

Sinh nhị phân bằng quay lui và dùng đếm phân phối để tính kết quả.

Độ phức tạp: $O(2^n)$.

Subtask 2

Sử dụng quy hoạch động cái túi, đặt $f(i,j)$ là xét tới $i$ có thể tạo ra được tổng $j$ hay không.

Ta có:

• $f(0,0) = \text{TRUE}$.
• $f(i,j) = f(i-1,j)$ | $f(i,j-a_i)$.

Độ phức tạp: $O\big(n \times sum(a_i)\big)$.

Subtask 3

Ta vẫn dùng quy hoạch động, nhưng cải tiến bằng bitset.

Đặt bitset < 1000001 > f[n], với bitset $f[i]$ lưu những tổng có thể tạo ra được khi xét tới $i$ (là những $bit$ $1$).

Ban đầu tất cả bitset đều có toàn bit $0,$ riêng $f[0][0] = 1$.

Ta có $f[i] = f[i-1]$ | $(f[i-1]$ << $a_i)$.

Phép toán $f[i-1]$ << $a_i$ có nghĩa là dịch bitset $f[i-1]$ đi $a_i$ bit, bởi nếu ta chọn cộng vào $a_i,$ thì ta sẽ tạo ra được các tổng mới từ $f[i-1]$ bằng cách thêm $a_i$ đơn vị. Do chúng ta đang lưu các tổng dưới dạng bit, nên đó chính là phép dịch $a_i$ bit.

Kết quả chính là số bit $1$ của $f[n]$ trừ đi $1,$ do ta không tính tập rỗng. Hay chính là $f[n]$.count() $- 1$.

Độ phức tạp: $O\left(n \times \frac{sum(a_i)}{64}\right)$, do các thao tác trên bitset nhanh gấp $64$ lần so với mảng.

Code mẫu

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+1;

void solution(int n, vector < int > &a) 
{
    bitset < maxn > f;
    for (int i = 0; i <= 1e6; ++i) 
        f[i] = 0;
    f[0] = true;
	
    for (int i = 1; i <= n; ++i) 
    {
        bitset < maxn > q = f;
        q <<= a[i];
        f |= q;
    } 

    cout << f.count() - 1<< endl;
}

main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
	
    vector < int > a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
		
    solution(n);
	
    return 0;
}

IV. Tài liệu tham khảo

• https://www.topcoder.com/thrive/articles/A bit of fun: fun with bits
• https://www.geeksforgeeks.org/bits-manipulation-important-tactics/
• https://en.wikipedia.org/wiki/Bit_manipulation
• https://codeforces.com/blog/entry/105301
• https://cplusplus.com/reference/bitset/bitset/

---

©️ Tác giả: Vũ Quế Lâm từ Viblo