Bội chính phương (THTB TQ 2020)
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 một dãy số \(A\) có \(N\) phần tử. Tìm số nguyên dương \(P\) nhỏ nhất thỏa mãn: \(P\) là số chính phương và \(P\) chia hết cho tất cả các phần tử của dãy số \(A\).
Yêu cầu: In ra phần dư của phép chia khi chia \(P\) cho \(10^9+7\)
Input
- Dòng đầu tiên chứa số nguyên dương \(N\) là số lượng phần tử của dãy số.
- Dòng tiếp theo chứa \(N\) số nguyên dương \(a_i\) là các phần tử của dãy số \(A\) \((1 \le i \le N)\)
Các số trên một dòng được ghi cách nhau bởi dấu cách
Output
= Ghi ra thiết bị ra chuẩn gồm một số nguyên duy nhất là kết quả của bài toán.
Example
Test 1
Input
3
2 1 3
Output
36
Scoring
- Subtask \(1\): Có \(30\%\) số test ứng với \(N \le 10\), \(a_i \le 10\)
- Subtask \(2\): Có \(30\%\) số test khác ứng với \(N \le 10^4\), \(a_i \le 10^5\)
- Subtask \(3\): Có \(40\%\) số test còn lại ứng với \(N \le 10^5\), \(a_i \le 10^7\)
Bình luận
Sử dụng sàng Eratos+phân tích thừa số nguyên tố+mảng max thừa số+lũy thừa nhị phân=AC
Bùn vì thấy top 10 sub if test hết :<
Hint: Các thừa số nguyên tố của một số chính phương đều có lũy thừa là số chẵn.
Ngoài phân tích thừa số nguyên tố còn cách nào nữa ko mọi người :()
Ai làm solve bài này đi ạ
dữ liệu vào nhìn tưởng đơn giản hóa ra không đơn giản chút nào, tốn chục lần nộp