Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VO17LAN - Hoa Ngọc Lan (7 điểm)

Để chuẩn bị cho kì thi VOI 2017, hai đội tuyển Hải Phòng và Hải Dương dắt tay nhau ra Hà Nội học Giáo Sư.

Saker vốn từ trước đến nay bị Lũ bạn sống lỗi ghét bỏ, nên khi cả đội ra Hà Nội, không ai cho Saker ở cùng phòng. Bí quá, Saker chẳng còn cách nào ngoài cách cầu xin hai bạn nữ đội Hải Phòng cho ở nhờ.

Để việc "xin xỏ tỏ tình" dễ bề thành công, trước khi đi, Saker hái một bó gồm N bông hoa Ngọc Lan. N bông hoa này có độ hấp dẫn là A1, A2, ..., AN. Saker cần phải chia bó hoa trên làm hai phần tặng cho hai bạn nữ.

Độ hấp dẫn của một phần được tính bằng ước số chung lớn nhất của độ hấp dẫn các bông hoa trong phần đó. Saker muốn chia số hoa hiện tại sao cho độ hấp dẫn của phần hoa kém hấp dẫn hơn là lớn nhất có thể. Tất nhiên, nếu Saker dành toàn bộ số hoa chỉ cho một người, chiến tranh thế giới sẽ nổ ra và hắn sẽ bị đuổi khỏi phòng đầu tiên.

Hãy giúp Saker thực hiện trót lọt ý đồ ám muội này.

Input

Dòng đầu tiên chứa một số nguyên T, là số bộ dữ liệu

Các dòng tiếp theo lần lượt mô tả các bộ dữ liệu. Mỗi bộ dữ liệu được mô tả trên hai dòng: Dòng đầu tiên chứa số N là số bông hoa, dòng thứ hai chứa N số nguyên dương A1, A2, ..., AN lần lượt là độ hấp dẫn của các bông hoa.

Output

Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên duy nhất là độ hấp dẫn tối đa của phần hoa kém hấp dẫn hơn.

Giới hạn

- Trong 25% số test đầu tiên, T <= 20, 2 <= N <= 15 và Ai <= 109.

- Trong 25% số test tiếp theo, T <= 20, 2 <= N <= 100 và Ai <= 270.

- Trong 50% số test còn lại, 2 <= N <= 50000, Ai <= 109 và tổng giá trị của N trong các test của môt file input không quá 200000.

Example

Input:
3 
5
4 9 8 6 20
10
2 2 2 3 3 3 3 3 3 3
14
44120320 584722489 449786530 269871918 944551713 764637101 1 719658448 714210560 293326080 629701142 502234240 207895680 713251840 Output: 3
2

Giải thích

Trong test thứ nhất, cách chia tối ưu là ta chia thanh hai tập A = {4, 8, 20} và B ={9, 6}. Khi đó, GCD(A) = 4 và GCD(B) = 3. min(GCD(A), GCD(B)) = 3 là đáp số cần tìm.


Được gửi lên bởi:VOJ Team
Ngày:2016-12-29
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VNOI Online 2017, day 2 & Russian Code Cup 2016 Qualification Round C

hide comments
2017-01-15 09:48:26 xin đừng quên tôi
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://yeulaptrinh.pw/658/vo17lan-spoj/
2017-01-15 09:46:50 GYC


Last edit: 2017-01-15 09:47:30
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.