trang chủ / đề bài / icpc26_nat_g

Dãy GCD

Đề bài

Mô tả

Với một dãy A gồm n số nguyên dương a1,a2,…,an, dãy GCD của nó là dãy B gồm n−1 số nguyên b1,b2,…,bn−1, trong đó bi=gcd(ai,ai+1).

Ví dụ, dãy GCD của A=[2,4,5,3,9] là B=[2,1,1,3].

Ở đây, gcd(x,y) là ước chung lớn nhất của hai số nguyên x và y, tức là số nguyên dương lớn nhất chia hết cả x và y. Ví dụ, gcd(12,18)=6.

Cho một dãy B gồm n−1 số nguyên dương. Hãy tìm một dãy A gồm n số nguyên dương có dãy GCD là B sao cho tổng a1+a2+…+an 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 τ (1≤τ≤104). 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 n (2≤n≤105), độ dài dãy A.

Dòng thứ hai chứa n−1 số nguyên b1,b2,…,bn−1 (1≤bi≤109).

Dữ liệu đảm bảo tổng n qua tất cả các bộ dữ liệu không vượt quá 105.

Dữ liệu ra

Với mỗi bộ dữ liệu, nếu không có dãy A nào có dãy GCD là B, in ra −1. Ngược lại, in ra n số nguyên a1,a2,…,an: một dãy có dãy GCD là B 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 ai trong một dãy có tổng nhỏ nhất đều không vượt quá 1018. Nếu có nhiều đáp án, bạn có thể in ra một đáp án bất kỳ.

Ràng buộc

  • 1≤τ≤104.
  • 2≤n≤105; 1≤bi≤109.
  • Tổng n qua tất cả các bộ dữ liệu không vượt quá 105.

Ví dụ

Input Output Giải thích
1
5
2 1 1 3
2 2 1 3 3 Dãy A=[2,4,5,3,9] có dãy GCD là [2,1,1,3] với tổng 23. Tuy nhiên, dãy A=[2,2,1,3,3] có cùng dãy GCD với tổng nhỏ hơn là 11, 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: gcd(4,4)=4. Bộ thứ hai: a2 và a3 đều phải chia hết cho 4 nên gcd(a2,a3) chia hết cho 4, không thể bằng 6. Bộ thứ ba: a2 phải chia hết cho cả 6 và 10 nên a2≥30.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0