THTBTQ22 Số chính phương
Xem PDF
Điểm:
1600 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho dãy số nguyên dương \(A\) gồm \(N\) phần tử \(a_1, a_2, \ldots, a_n\). Với phần tử \(a_i\) là số chính phương \(s\) lớn nhất thõa mãn: khi thay \(a_i\) thành \(a_i \times s\) thì bội chung nhỏ nhất của dãy số \(A\) là không đổi.
Yêu cầu: Cho dãy số \(A\) và vị trí \(i\), tìm số chính phương kết hợp của phần tử \(a_i\).
Input
- Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(i\) (\(1 \le N \le 10^6\)).
- Dòng thứ hai gồm \(N\) số nguyên mô tả dãy số \(A\), các số có giá trị không quá \(10^7\).
Output
- Ghi ra thiết bị ra chuẩn bị một dòng gồm một số nguyên duy nhất là phần dư của kết quả tìm được khi chia cho \(10^9 + 7\)
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(N \le 20\), \(a_i \le 20\).
- Subtask \(2\) (\(30\%\) số điểm): \(N \le 10^3\), \(a_i \le 10^7\).
- Subtask \(3\) (\(20\%\) số điểm): không có ràng buộc gì thêm.
Example
Test 1
Input
5 2
8 4 6 18 5Output
9Note
- Bội chung nhỏ nhất của dãy số A là 360.
- Thay số \(4\) thành \(4 \times 9 = 36\) thì dãy số là \(8\), \(36\), \(6\), \(18\), \(5\) vẫn có bội chung nhỏ nhất là 360.
- Vậy kết quả là 9
Bình luận
test 5 có sai không , mà sao mình toàn AC hết , mỗi test 5 làm kiểu gì cũng sai
test có sai ko vậy mn
how to do it ?
Bài này có ý tưởng gì ko namhoangtu phongduongLOL
sao đề bài kêu mỗi số A trong dãy đều có giá trị không quá 1e7 nhưng sao trong vài test lại dãy A lại có giá trị lớn hơn 1e7 vậy ạ?