D. Ghd

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Жон Дөе эгч Жэйн Дөе-дөө $а$ тоон олонлогын gcd-г олохыг санал болгов.

Gcd бол олонлог дахь бүх тоонуудыг зэрэг хуваадаг $g$ гэсэн бүхэл тоо бөгөөд, бүх тоонуудыг зэрэг хуваадаг $g'$ ($g' > g$) тоо оршихгүй болно.

Харамсалтай нь Жэйн даалгаварыг гүйцэтгэж чадаагүй тул Жон түүнд уг олонлогыг ghd-г олохыг санал болгожээ.

Ghd бол олонлогын элементүүдийн дор хаяж хагасыг нь зэрэг хуваадаг $g$ гэсэн бүхэл тоо юм. Мөн бүх тоонуудыг зэрэг хуваадаг $g'$ ($g' > g$) тоо байхгүй болно.

Жэйн уг даалгаварт 2 цаг зарцуулжээ. Та ч бас оролдоод үзээрэй.

Оролт

Эхний мөрөнд $а$ олонлог хичнээн элементтэйг илэрхийлэх $n$ ($1 ≤ n ≤ 10^6$) бүхэл тоо байна.

2 дахь мөрөнд хоосон зайгаар тусгаарлагдсан $a_1, a_2, ... , a_n$ ($1 ≤ a_i ≤ 10^{12})$ бүхэл тоонууд байна. Өгөгдсөн олонлог тэнцүү элементтэй байж болохыг анхаараарай.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Гаралт

$a$ олонлогын ghd болох $g$ тоог хэвлэнэ.

Орчуулсан: Энхдүүрэн

Жишээ тэстүүд

Оролт
6
6 2 3 4 5 6
Гаралт
3
Оролт
5
5 5 6 10 15
Гаралт
5
Сэтгэгдлүүдийг ачааллаж байна...