Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
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