Bài 33.3. Thử Thách Cấu Trúc Gen Đặc Biệt - [Độ khó: Khá]

Mô tả: Trong một dự án sinh học máy tính, các nhà khoa học đang phân loại các chuỗi gen, được biểu diễn bằng các số nguyên dương. Một "gen đặc biệt" được định nghĩa là một số nguyên dương có chính xác K ước số nguyên tố phân biệt. Ví dụ:

• Số 12 = \(2^2 \times 3^1\) có 2 ước số nguyên tố phân biệt (2 và 3).
• Số 30 = \(2 \times 3 \times 5\) có 3 ước số nguyên tố phân biệt (2, 3 và 5).
• Số 7 có 1 ước số nguyên tố phân biệt (7).
• Số 1 có 0 ước số nguyên tố phân biệt.

Bạn được yêu cầu xây dựng một hệ thống để giúp các nhà khoa học đếm số lượng "gen đặc biệt" trong các đoạn số khác nhau.

INPUT FORMAT

Dòng đầu tiên chứa số nguyên MaxN (\(1 \le MaxN \le 10^6\)), là giới hạn trên của các số gen. Dòng thứ hai chứa số nguyên Q (\(1 \le Q \le 10^5\)), là số lượng truy vấn. Q dòng tiếp theo, mỗi dòng chứa ba số nguyên L, R, K (\(1 \le L \le R \le MaxN\), \(0 \le K \le 7\)).

OUTPUT FORMAT

Với mỗi truy vấn, in ra một số nguyên duy nhất trên một dòng, là số lượng các số X thỏa mãn L <= X <= R và X có chính xác K ước số nguyên tố phân biệt.

Ví dụ:

Input:

30
3
1 10 1
10 20 2
1 30 3

Output:

7
6
1

Giải thích:

• Số lượng ước số nguyên tố phân biệt (cdpf) của các số từ 1 đến 30:

  • cdpf(1) = 0, cdpf(2) = 1, cdpf(3) = 1, cdpf(4) = 1, cdpf(5) = 1, cdpf(6) = 2, cdpf(7) = 1, cdpf(8) = 1, cdpf(9) = 1, cdpf(10) = 2
  • cdpf(11) = 1, cdpf(12) = 2, cdpf(13) = 1, cdpf(14) = 2, cdpf(15) = 2, cdpf(16) = 1, cdpf(17) = 1, cdpf(18) = 2, cdpf(19) = 1, cdpf(20) = 2
  • cdpf(21) = 2, cdpf(22) = 2, cdpf(23) = 1, cdpf(24) = 2, cdpf(25) = 1, cdpf(26) = 2, cdpf(27) = 1, cdpf(28) = 2, cdpf(29) = 1, cdpf(30) = 3

• Truy vấn 1 (1 10 1): Các số trong đoạn [1, 10] có chính xác 1 ước số nguyên tố phân biệt là: 2, 3, 4, 5, 7, 8, 9. Tổng cộng có 7 số.

• Truy vấn 2 (10 20 2): Các số trong đoạn [10, 20] có chính xác 2 ước số nguyên tố phân biệt là: 10, 12, 14, 15, 18, 20. Tổng cộng có 6 số.
• Truy vấn 3 (1 30 3): Số duy nhất trong đoạn [1, 30] có chính xác 3 ước số nguyên tố phân biệt là: 30. Tổng cộng có 1 số.