Hô li đây @ Đà Nẵng
Submit solution
Points:
1
Time limit:
1.0s
Memory limit:
500M
Author:
Problem type
Allowed languages
Assembly, C, C++, Java, Pascal, Perl, Python, Text
Giữa năm lớp 11, cậu cùng lớp có một chuyến du lịch tới Đà Nẵng. Trong một buổi chiều trời sắp mưa, cả lớp kéo nhau ra biển Mỹ Khê để tổ chức teambuilding. Cả lớp được chia làm \(N\) nhóm, đánh số từ 1 đến \(N\). Ban đầu, nhóm thứ \(i\) sở hữu \(a_i\) điểm thưởng.
Để tăng tính đồng đội và tạo sự bất ngờ, ban tổ chức đưa ra quy tắc "Giao lưu điểm số" kéo dài trong \(K\) vòng chơi. Ở mỗi vòng:
- Tất cả các nhóm đồng thời tính toán số điểm mới \(B_i\) cho nhóm mình. Điểm \(B_i\) bằng tổng số điểm hiện tại của tất cả các nhóm \(j\) thỏa mãn \(\gcd(i, j) = 1\).
- Sau khi tính xong \(B_i\), số điểm của tất cả các nhóm đồng loạt cập nhật thành: \(a_i \leftarrow B_i\) để bước vào vòng tiếp theo.
Hãy tính tổng số điểm của từng nhóm sau đúng \(K\) vòng giao lưu.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên dương \(N, K \ (1\le N \le 100; 1\le K \le 10^{18})\);
- Dòng tiếp theo chứa \(N\) số nguyên \(a_i \ (1 \le a_i \le 10^9)\).
Kết quả
- In ra \(N\) số nguyên, là điểm số của từng nhóm, sau khi chia lấy dư cho \(10^9+7\), trên một dòng. Mỗi số nguyên cách nhau bởi một dấu cách trống.
Chấm điểm
- Subtask 1 (40%): \(K \le 10^3\).
- Subtask 2 (30%): \(K \le 10^6\).
- Subtask 3 (30%): Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
3 2
1 1 1
output
7 5 5
Giải thích
Sau lượt đầu tiên, điểm số của các đội là 3, 2, 2.
Sau lượt thứ hai, điểm số của các đội là 7, 5, 5.
Comments