Dãy GCD
Đề bài
Mô tả
Với một dãy gồm số nguyên dương , dãy GCD của nó là dãy gồm số nguyên , trong đó .
Ví dụ, dãy GCD của là .
Ở đây, là ước chung lớn nhất của hai số nguyên và , tức là số nguyên dương lớn nhất chia hết cả và . Ví dụ, .
Cho một dãy gồm số nguyên dương. Hãy tìm một dãy gồm số nguyên dương có dãy GCD là sao cho tổng nhỏ nhất, hoặc cho biết không tồn tại dãy như vậy.
Dữ liệu vào
Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu (). Tiếp theo là mô tả các bộ dữ liệu.
Dòng đầu tiên của mỗi bộ dữ liệu chứa số nguyên (), độ dài dãy .
Dòng thứ hai chứa số nguyên ().
Dữ liệu đảm bảo tổng qua tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, nếu không có dãy nào có dãy GCD là , in ra . Ngược lại, in ra số nguyên : một dãy có dãy GCD là với tổng nhỏ nhất.
Có thể chứng minh rằng nếu tồn tại dãy như vậy thì mọi trong một dãy có tổng nhỏ nhất đều không vượt quá . Nếu có nhiều đáp án, bạn có thể in ra một đáp án bất kỳ.
Ràng buộc
- .
- ; .
- Tổng qua tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 5 2 1 1 3 |
2 2 1 3 3 | Dãy có dãy GCD là với tổng . Tuy nhiên, dãy có cùng dãy GCD với tổng nhỏ hơn là , và đây là tổng nhỏ nhất. |
| 3 2 4 4 4 6 4 3 6 10 |
4 4 -1 6 30 10 |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: . Bộ thứ hai: và đều phải chia hết cho nên chia hết cho , không thể bằng . Bộ thứ ba: phải chia hết cho cả và nên . |
Bình luận