Задача: Игра в камушки
Маша и Даша играют в игру с N (\(1<=N<=10^5\)) кучками камушков, где i-ая кучка содержит ai камешков (\(1<=i<=N\), \(1<=a_i<=10^6\)). Они ходят по очереди, первой ходит Маша.
- Сначала Маша выбирает некоторое положительное число
s1 и удаляет s1 камешков из некоторой кучки, в которой есть не менее s1 камешков.
- Затем Даша выбирает некоторое положительное число
s2 такое, что s2 делится на s1 и удаляет s2 камешков из некоторой кучки, содержащей не менее s2 камешков.
- Затем Маша выбирает некоторое положительное число
s3, которое делится на s2 и удаляет s3 камешков из некоторой кучки, в которой есть не менее s3 камешков.
- В общем случае
si, количество камешков, которое убирается на ходу i, должно быть делителем si+1.
Проигрывает тот, кто не может сделать ход.
Вычислите количество способов, которыми Маша может удалить камешки на первом ходу для того, чтобы гарантировать себе победу (то есть существет стратегия, используя которую Маша победит вне зависимости от ходов Даши). Два способа удаления камешков называются различными, если они удаляют различное количество камушков или они удаляют камешки из различных кучек.
Входные данные
Первая строка содержит
N.
Вторая строка содержит
N разделённых одиночными пробелами целых чисел
a1,…,
aN.
Выходные данные
Выведите количество способов, которыми Маша может удалить камушки на первом ходу, чтобы гарантировать себе выигрыш.
Для вычислений используйте 64-ное целое например, "
long long" в C/C++.
Примеры
| № |
Входные данные |
Выходные данные |
Примечание |
| 1 |
1
7 |
4 |
Маша выбирает 4, 5, 6, 7 камушков из одной кучи и игра закончится сразу. |
| 2 |
6
3 2 3 2 3 1 |
8 |
Маша выиграет, если удалит 2 или 3 камушка из любой кучи. Затем игроки будут по очереди брать одно и то же количество камушков, но Маша сделает последний ход. |
Ваш ответ: