Lời giải

Các giá trị ~a_i~ có thể trùng nhau. Nếu một giá trị xuất hiện ít nhất hai lần thì bản thân giá trị đó đã là một ước chung của cặp đó.

Xét mọi cặp cần tới ~n^2/2 = 2 \cdot 10^{10}~ phép tính ~\gcd~ nên chắc chắn quá thời gian.

Hãy làm ngược lại: với mỗi ~d~ từ lớn đến nhỏ, đếm xem trong mảng có bao nhiêu phần tử là bội của ~d~. Ngay khi tìm được ~d~ có ít nhất hai bội thì ~d~ chính là đáp án. Tổng chi phí đếm bội cho mọi ~d~ chỉ là ~O(V \log V)~ với ~V = 10^6~.