Bedao Regular Contest 15 - SQUARELCM
Xem dạng PDF
Cho dãy gồm ~n~ số nguyên dương ~a_1~, ~a_2~, ..., ~a_n~. Bạn có quyền thay đổi các phần tử của dãy số này sao cho ~\forall i~ ~(1 \le i < n)~ ~LCM(a_i, a_{i+1})~ là các số chính phương.
Tại mỗi bước thay đổi, bạn chọn một vị trí ~i~ bất kì (~1 \leq i \leq n~) và cập nhật ~a_i~ := ~a_i \times x~ với ~x~ là một số nguyên dương bất kì. Không giới hạn số lần thay đổi của một phần tử.
Hãy tính số lần thay đổi tối thiểu để thỏa mãn yêu cầu đề bài.
Input
Dòng đầu gồm số nguyên dương ~n~ ~(1 \le n \le 2 \times 10^5)~.
Dòng thứ hai gồm ~n~ số nguyên dương ~a_i~ ~(1 \le a_i \le 10^9)~.
Output
- Gồm một số nguyên không âm duy nhất là kết quả của đề bài.
Scoring
Subtask ~1~ (~30~ điểm): ~n \le 1000~, ~a_i \le 5~ ~\forall~ ~1 \le i \le n~.
Subtask ~2~ (~70~ điểm): Không có điều kiện gì thêm.
Sample Input 1
4
6 4 2 3
Sample Output 1
2
Sample Input 2
4
4 1 2 3
Sample Output 2
1
Notes
Ta có thể thay đổi dãy thành ~[162, 4, 2, 36]~ sau khi thay đổi phần tử đầu tiên và phần tử cuối cùng.
Bình luận
Mình có cái hint này giúp các bạn làm bài trên dễ hơn nè. Thay đổi đk của bài thành: "Tìm kiếm tối thiểu có bao nhiêu số mà LCM() của nó ko phải là số chính phương". Chúc các bạn code vui vẻ và mình là ZenoCode 😊