images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
19/04/2024 22:32:49

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2380. НОД подпоследовательностей

Ограничения: время – 2000ms/4000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Наибольший общий делитель (НОД) двух чисел может вычислен по формуле:
НОД(a,b)=a, если b=0;
НОД(a,b)=НОД(b, a mod b), если b>0.
НОД нескольких чисел вычисляется последовательным применением НОД к парам чисел:
НОД(a,b,c)=НОД(НОД(a,b),c)
НОД(a)=a
Напишите программу, которая находит НОД для всех непрерывных подпоследовательностей `a_i,\ a_{i+1},\ …,\ a_j` (где `1\ ≤\ i\ ≤\ j\ ≤\ N`) в заданной последовательности `a_1,\ a_2,\ …,\ a_N` и определяет количество различных значений среди них.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 500000`). Вторая строка ввода содержит `N` целых чисел в диапазоне от 1 до `10^18`, разделенных пробелами – последовательность `a_1,\ a_2,\ …,\ a_N`.
Вывести одно целое число – количество различных значений среди НОД для всех непрерывных подпоследовательностей в заданной последовательности.

Пример ввода 1

4
9 6 2 4

Пример вывода 1

6

Пример ввода 2

4
9 6 3 4

Пример вывода 2

5
Пояснение к примеру 1:
НОД(9)=9; НОД(6)=6; НОД(2)=2; НОД(4)=4; НОД(9, 6)=3; НОД(6, 2)=2; НОД(2, 4)=2; НОД(9, 6, 2)=1; НОД(6, 2, 4)=2; НОД(9, 6, 2, 4)=1
Из этих 10 значений различными являются 1, 2, 3, 4, 6, 9.
Описание подзадач и системы оценивания
Подзадача 1 (30 баллов)
`1\ ≤\ N\ ≤\ 1000`, числа от 1 до `10^6`
В этой подзадаче 6 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (20 баллов)
`2\ ≤\ N\ ≤\ 1000`, числа от 1 до `10^18`
Необходимые подзадачи: 1.
В этой подзадаче 4 теста, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 3 (25 баллов)
`1000\ <\ N\ ≤\ 100000`, числа от 1 до `10^6`
Необходимые подзадачи: 1.
В этой подзадаче 5 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 4 (25 баллов)
`100000\ ≤\ N\ ≤\ 500000`, числа от 1 до `10^18`
Необходимые подзадачи: 1,2,3.
В этой подзадаче 25 тестов, каждый тест оценивается в 1 балл. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.
loading