408324: GYM103092 J Just One Left
Description
Диас и Арыстан интересуются спортивным программированием и хотят попасть в ACM Club нашего чудесного SDU. Для этого они сходили на выставку клубов и выяснили, что туда попадают только те, кто готовят первоклассный маклюбе и способны решить одну непростую задачу. Диас и Арыстан не могли похвастаться кулинарными навыками и решили сначала научиться готовить, а вас попросили помочь с решением задачи, условие которой описано ниже.
Вам дан массив $$$a$$$ длины $$$n$$$ состоящий из положительных целых чисел. Обозначим $$$f(a)$$$ как массив $$$b$$$ длины $$$n-1$$$, где $$$b_i = gcd(a_1 + \dots + a_i, a_{i+1} + \dots + a_n)$$$. Будем применять операцию $$$a = f(a)$$$ до тех пор, пока размер массива $$$a$$$ не станет равным $$$1$$$. Выведите единственное оставшееся число в массиве.
Здесь $$$gcd(x, y)$$$ означает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.
Входные данныеВ первой строке задано одно целое число $$$n$$$ – длина исходного массива ($$$2 \le n \le 10^{5}$$$).
Во второй строке набора записаны $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ — элементы исходного массива $$$a$$$ ($$$1 \le a_i \le 10^9$$$).
Выходные данныеВыведите одно целое число — единственное оставшееся число в массиве.
ПримерВходные данные3 4 6 8Выходные данные
2Примечание
Пояснение для первого примера:
- $$$a = [4, 6, 8]$$$
- $$$f(a) = [gcd(4, 14)$$$, $$$gcd(10, 8)]$$$ = $$$[2, 2]$$$
- $$$f(f(a)) = [gcd(2, 2)] = 2$$$