Link đề gốc : http://vnoi.info/problems/show/VO17LAN/
Đề bài
Để 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, …, ANlầ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<= 109và tổng giá trị của N trong các test của môt file input không quá 200000.