Tổng các BCNN
Đề bài
Mô tả
Cho dãy gồm số nguyên dương.
Xét tất cả các tập con khác rỗng của dãy và tính bội chung nhỏ nhất (BCNN, tiếng Anh: LCM) của các phần tử trong mỗi tập con. Hãy tính tổng tất cả các giá trị BCNN đó.
Hai tập con được coi là khác nhau nếu chúng chọn các tập vị trí khác nhau (các phần tử bằng nhau ở các vị trí khác nhau vẫn được tính riêng). Vì kết quả có thể rất lớn, hãy in ra phần dư của tổng khi chia cho .
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương (): số bộ test.
- Mỗi bộ test gồm:
- một dòng chứa số nguyên dương ();
- tiếp theo là số nguyên dương (), cách nhau bởi dấu cách hoặc xuống dòng.
Dữ liệu ra
In ra dòng, mỗi dòng chứa một số nguyên: đáp án của bộ test tương ứng.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 5 1 1 1 1 1 3 1 2 3 6 4 4 4 2 2 2 10 9 5 12 58 1 85 24 90 100 99 |
31 23 238 651657343 |
Ví dụ của đề gốc. Bộ test thứ nhất có tập con khác rỗng, mỗi tập có BCNN bằng . Bộ test thứ hai: . |
| 3 1 6 2 23 46 2 256 3 |
6 115 1027 |
Ví dụ bổ sung, tính bằng lời giải mẫu. Bộ test thứ hai: . Bộ test thứ ba: . |
Bình luận