Bài 1. Trò chơi với dãy số (HSG THPT Thành phố Huế 2026)
Xem dạng PDFToán học là một môn học rất quan trọng và có nhiều ứng dụng trong cuộc sống. Tuy nhiên, một số bạn cho rằng môn học này khó khăn và khó tiếp thu. Biết được điều đó, sau tiết học về luỹ thừa, thầy giáo đã thiết kế một trò chơi để học sinh hiểu thêm về bài học. Trò chơi được mô tả như sau:
Cho một dãy ~A~ gồm ~N~ số nguyên dương đôi một khác nhau và một số nguyên dương ~k~. Mỗi bạn sẽ chọn một số ~x~ bất kỳ trong dãy ~A~, mỗi số chỉ được chọn một lần. Nếu trong dãy đã cho tồn tại các số có giá trị ~x^2, x^3, \ldots, x^k~ (không quan tâm đến vị trí xuất hiện của các số trong dãy) thì bạn đó sẽ nhận được một phần thưởng.
Đếm xem có tối đa bao nhiêu bạn nhận được phần thưởng.
Dữ liệu vào
Gồm hai dòng:
- Dòng 1: Chứa hai số nguyên ~N, k (1 \le N \le 10^5, 1 \le k \le 10^5)~.
- Dòng 2: Chứa ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~ tương ứng ~N~ phần tử của dãy số ~A (1 \le a_i \le 10^5)~.
Kết quả
Một dòng duy nhất là kết quả của bài toán.
Ví dụ
Input 1
9 3
1 2 3 4 8 9 16 32 64
Output 1
3
Học sinh chọn một trong ba số 1, 2, 4 sẽ nhận được phần thưởng: với ~x = 1~ thì ~1^2 = 1^3 = 1~ đều có trong dãy; với ~x = 2~ thì 4 và 8 có trong dãy; với ~x = 4~ thì 16 và 64 có trong dãy. Số 3 không được vì 27 không có trong dãy.
Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).