UNITGCD - Unit GCD

Link đề bài - Link bản tiếng Việt

Tóm tắt đề bài: bạn có 1 quyển sách được đánh số từ 1 đến N. Mỗi ngày bạn được đọc một số trang nhất định sao cho chỉ số của các trang đó là các cặp số nguyên tố cùng nhau. Tìm số ngày ít nhất để đọc hết cuốn sách cũng như cách đọc trong từng ngày. Chú ý là mỗi ngày bạn được đọc một số trang sao cho chỉ số của các trang đó là các cặp số nguyên tố cùng nhau, nghĩa là mỗi ngày bạn phải đọc ít nhất là 2 trang.

Hướng dẫn giải: Đây là Nguyên lý Chuồng bồ câu (hay Nguyên lý Dirichlet) trong Toán rời rạc. Từ 1 đến N, cứ 2 số nguyên liên tiếp sẽ tạo thành 1 cặp số nguyên tố cùng nhau. Số ngày tối thiểu để đọc hết N trang sách là trang - cũng là số cặp số nguyên tố cùng nhau không lặp lại có thể chia được. Trong đó, trường hợp N lẻ chúng ta có tập kết quả lớn nhất gồm 3 phần tử {1, 2, 3}, còn lại là các cặp nguyên tố cùng nhau. Công việc cần là phân loại theo điều kiện N và in kết quả ra thôi.

CU;WTF (Cannot Understand, WTF?): in ra các tập 2 phần tử. Ví dụ: N = 4 => {1, 2}, {3, 4}. Nếu N lẻ thì in 3 phần tử đầu rồi cứ in 2 phần tử làm tới. VD: N = 5 => {1, 2, 3}, {4, 5}; N = 9 => {1, 2, 3}, {4, 5}, {6, 7}, {8, 9}. Chú ý trường hợp N = 1 thì chỉ in ra 1 phần tử thôi.

Code mẫu (C++)

Happy coding!