Игра с камнями
Игра с камнями
Беси и Эльза играют в игру с n кучками камушков, где i-ая (1 ≤ i ≤ n) кучка содержит ai
камешков (1 ≤ ai
≤ 106
). Они ходят по очереди, первой ходит Беси.
- Сначала Беси выбирает некоторое положительное число
s1
и удаляетs1
камешков из некоторой кучки, в которой есть не менееs1
камешков - Затем Эльза выбирает некоторое положительное число
s2
такое, чтоs2
делится наs1
и удаляетs2
камешков из некоторой кучки, содержащей не менееs2
камешков. - Затем Беси выбирает некоторое положительное число
s3
, которое делится наs2
и удаляетs3
камешков из некоторой кучки, в которой есть не менееs3
камешков - В общем случае
si
, количество камешков, которое убирается на ходу i, должно быть делителемsi+1
.
Проигрывает первая корова, которая не может сделать ход.
Вычислите количество способов, которыми Беси может удалить камешки на первом ходу для того, чтобы гарантировать себе победу (то есть существет стратегия, используя которую Беси победит вне зависимости от ходов Эльзы). Два способа удаления камешков называются различными, если они удаляют различное количество камушков или они удаляют камешки из различных кучек.
Входные данные
Первая строка содержит n (1 ≤ n ≤ 105
).
Вторая строка содержит n целых чисел a1
,..., an
.
Выходные данные
Выведите количество способов, которыми Беси может удалить камушки на первом ходу, чтобы гарантировать себе выигрыш.
Для вычислений используйте 64-ное целое например, "long long" в C/C++.
Пример 1
Беси выиграет 4, 5, 6, 7 камушков из одной кучи и игра закончится сразу.
Пример 2
Беси выиграет, если удалит 2 или 3 камушка из любой кучи. Затем игроки будут по очереди брать одно и то же количество камушков, но Беси сделает последний ход.
1 7
4
6 3 2 3 2 3 1
8