Ước chung lớn nhất
Đề bài
Mô tả
Cho dãy số gồm số nguyên dương (), số thứ có giá trị ().
Xét tất cả các tập con khác rỗng của dãy (hai phần tử ở hai vị trí khác nhau được coi là khác nhau, kể cả khi bằng giá trị), với mỗi tập con ta tính ước chung lớn nhất của các số trong tập. Hỏi tổng các ước chung lớn nhất của tất cả các tập con là bao nhiêu? Vì kết quả rất lớn, chỉ cần in ra phần dư của nó khi chia cho .
Dữ liệu vào
Dòng đầu tiên chứa số nguyên dương (): số bộ dữ liệu. Tiếp theo là bộ dữ liệu, mỗi bộ gồm:
- Dòng đầu tiên chứa số nguyên dương .
- Dòng thứ hai chứa số nguyên dương, số thứ là .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên là đáp án của bộ dữ liệu đó.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 5 1 1 1 1 1 3 1 2 3 |
31 10 |
Bộ thứ nhất: mọi số đều bằng nhau nên mọi tập con có ước chung lớn nhất là ; có tập con khác rỗng nên tổng là . Bộ thứ hai: các tập con khác rỗng có ước chung lớn nhất lần lượt là , tổng bằng . |
| 2 3 4 6 70 1 70 |
88 70 |
Bộ thứ nhất: cho ba tập một phần tử, mọi tập có từ hai phần tử trở lên có ước chung lớn nhất là , tổng . Bộ thứ hai chỉ có tập . |
Bình luận