LTOJ Challenge 03

Cho hai số tự nhiên \(K\) và \(N\). Xét dãy số vô hạn được tạo theo quy luật:

• \(K\) số đầu tiên đều bằng \(1\);
• \(K\) số tiếp theo đều bằng \(2\);
• \(K\) số tiếp theo đều bằng \(3\);
• ...
  Ví dụ, với \(K = 2\), dãy số là: \(1, 1, 2, 2, 3, 3, 4, 4, \ldots\)

Yêu cầu

Hãy tính tổng của \(N\) số đầu tiên của dãy. Vì kết quả có thể rất lớn, chỉ cần in ra hai chữ số cuối cùng của kết quả.

Dữ liệu vào

Dữ liệu được đọc từ tệp TONGDAYSO.INP có cấu trúc như sau:
Gồm hai dòng:

• Dòng thứ nhất chứa số tự nhiên \(K\).
• Dòng thứ hai chứa số tự nhiên \(N\).
  Giới hạn: \(1 \le K, N \le 10^{12}\).

Kết quả

Dữ liệu được ghi ra tệp TONGDAYSO.OUT có cấu trúc như sau:
In ra hai chữ số cuối cùng của tổng cần tìm.

2
5

9

Số nguyên dương \(x\) được gọi là số \(k\) ước nếu \(x\) có thể biểu diễn dưới dạng tích của đúng \(k\) số nguyên tố. Một thừa số nguyên tố được tính theo số lần xuất hiện trong tích.

Yêu cầu

Cho \(q\) truy vấn. Mỗi truy vấn gồm ba số nguyên \(n\), \(m\), \(k\). Với mỗi truy vấn, hãy xác định có bao nhiêu số \(k\) ước nằm trong đoạn \([n,m]\), kể cả hai đầu đoạn.

Dữ liệu vào

Dữ liệu được đọc từ tệp KDIV.INP có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên \(q\) (\(1 \le q \le 10^5\)).
• Mỗi dòng trong \(q\) dòng tiếp theo chứa ba số nguyên \(n\), \(m\), \(k\) xác định một truy vấn (\(2 \le n \le m \le 10^5\), \(1 \le k \le 16\)).

Kết quả

Dữ liệu được ghi ra tệp KDIV.OUT có cấu trúc như sau:

Gồm \(q\) dòng, mỗi dòng chứa một số nguyên là kết quả của truy vấn tương ứng.

5
21 40 1
46 65 9
50 100 2
100 150 3
150 200 4

4
0
17
12
7

Cho ba số nguyên dương \(K\), \(a\) và \(b\). Từ dãy số vô hạn \(1, 2, 3, 4, \ldots\), hãy loại bỏ tất cả các số chia hết cho \(a\) hoặc \(b\). Xác định số ở vị trí thứ \(K\) trong dãy còn lại sau khi loại bỏ.

Dữ liệu vào

Dữ liệu được đọc từ tệp THUTHACH.INP có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên \(T\) (\(1 \le T \le 10^5\)), là số lượng truy vấn.
• \(T\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(K\), \(a\), \(b\) (\(1 \le K \le 10^9\), \(2 \le a, b \le 10^9\)) mô tả một truy vấn.

Kết quả

Dữ liệu được ghi ra tệp THUTHACH.OUT có cấu trúc như sau:

Gồm \(T\) dòng, mỗi dòng chứa kết quả của truy vấn tương ứng.

2
2 2 4
2 3 4

3
2

2
10 2 5
15 3 9

23
22

Một nhóm gồm \(n\) sinh viên tham gia một chuyến team-building. Các sinh viên đứng thành một hàng ngang theo thứ tự ban đầu.

Hãy chia các sinh viên thành một số nhóm sao cho:

• Mỗi nhóm gồm các sinh viên đứng liên tiếp trong hàng ban đầu.
• Chênh lệch giữa số nam và số nữ trong mỗi nhóm không vượt quá \(k\).

Đếm số cách chia nhóm thỏa mãn các điều kiện trên. Hai cách chia được xem là khác nhau nếu tồn tại hai sinh viên thuộc cùng một nhóm ở cách chia này nhưng không cùng nhóm ở cách chia kia.

Dữ liệu vào

Dữ liệu được đọc từ tệp TEAMBUILDING.INP có cấu trúc như sau:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \le k \le n \le 5000\)).
• Dòng thứ hai chứa xâu nhị phân độ dài \(n\): ký tự 1 biểu thị sinh viên nam, ký tự 0 biểu thị sinh viên nữ.

Kết quả

Dữ liệu được ghi ra tệp TEAMBUILDING.OUT có cấu trúc như sau:

In ra số cách chia nhóm, lấy phần dư theo \(10^9 + 7\).

4 1
1011

5