Quý Mão 2023
Xem PDF
Điểm:
1500 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Vì quá mệt khi phải tìm ý tưởng để viết cốt truyện cho đề ôn Tin học trẻ lần này, Quý quyết định chọn 1 bài tập ngẫu nhiên để làm giải trí. Bài tập mà Quý chọn có đề bài như sau:
Cho \(1\) dãy \(A\) gồm \(n\) số nguyên dương và \(1\) số \(e\). Hãy đếm số cặp \((i,k)\) thỏa mãn các điều kiện sau:
- \(1 \le i, k\)
- \(i + e \times k \le n\)
- Tích \(a_i \times a_{i + e} \times a_{i + 2e} \times ... \times a_{i + ke}\) là 1 số nguyên tố
Nhắc lại, số nguyên tố là số lớn hơn \(1\) và chỉ có \(2\) ước dương là \(1\) và chính nó.
Tuy nhiên, Quý đã không còn đủ sức để làm được bài này nên muốn nhờ các bạn hãy thay Quý giải bài tập trên.
Input
- Dòng đầu tiên gồm số nguyên \(t\) (\(t \le 10\)) là số lượng test cases của bài toán.
Mỗi test có cấu trúc như sau:
- Dòng đầu tiên bao gồm \(2\) số nguyên dương \(n\) và \(e\) (\(1 \le e \le n \le 10^5\)) là kích thước của mảng \(A\) và số \(e\) đề bài cho.
- Dòng thứ \(2\) bao gồm \(n\) số nguyên dương \(a_1, a_2, a_3, ..., a_n\) \((a_i \le 10^6)\)
Output
- Với mỗi test, in ra \(1\) số nguyên là số lượng cặp (\(i\), \(k\)) thỏa mãn điều kiện đề bài trên một dòng.
- In ra tổng cộng \(t\) dòng cho \(t\) test.
Scoring
- Subtask \(1\) (\(30\%\) số điểm): \(n, e \le 200, a_i \le 10^3\)
- Subtask \(2\) (\(30\%\) số điểm): \(e = 1, n \le 10^5, a_i \le 10^3\)
- Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm
Sample
Input
6
7 3
10 2 1 3 1 19 3
3 2
1 13 1
9 3
2 4 2 1 1 1 1 4 2
3 1
1 1 1
4 1
1 2 1 1
2 2
1 2Output
2
0
4
0
5
0
Bình luận
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Xin ý tưởng (ngoài contest) thì được chứ chép code với if test là không được bạn nhé 😃
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.