3571. [USACO21Feb Gold]Stone Game

【题目描述】

Bessie 和 Elsie 正在用 $N$（$1\le N\le 10^5$）堆石子进行一个游戏，其中对于每个 $1\le i\le N$，第 $i$ 堆石子有 $a_i$ 个石子（$1\le a_i\le 10^6$）。两头奶牛交替行动，Bessie 先手。

• 首先，Bessie 选择某个正整数 $s_1$ 并从至少包含 $s_1$ 个石子的某堆石子中取走 $s_1$ 个石子。
• 然后 Elsie 选择某个正整数 $s_2$，使得 $s_1$ 整除 $s_2$，并从至少包含 $s_2$ 个石子的某堆石子中取走 $s_2$ 个石子。
• 然后 Bessie 选择某个正整数 $s_3$，使得 $s_2$ 整除 $s_3$，并从至少包含 $s_3$ 个石子的某堆石子中取走 $s_3$ 个石子，以此类推。
• 总的来说，第 $i$ 回合中取走的石子数量 $s_i$ 必须整除 $s_{i+1}$。

第一个无法在其回合中取走石子的奶牛为失败者。

计算可以令 Bessie 必胜（表示存在一种策略，无论 Elsie 如何行动，Bessie 均可获胜）的第一回合取石子的方法数。如果两种取石子的方法中取的石子数量不同或者取的石子堆不同，则认为是两种不同的取石子的方法。

【输入格式】

输入的第一行包含 $N$。

第二行包含 $N$ 个空格分隔的整数 $a_1,\ldots,a_N$。

【输出格式】

输出可以令 Bessie 必胜（表示存在一种策略，无论 Elsie 如何行动，Bessie 均可获胜）的第一回合取石子的方法数。

注意这个问题涉及到的整数大小可能需要使用 64 位整数型存储（例如，C/C++ 中的 long long）。

【样例输入1】

1
7

【样例输出1】

4

【样例输入2】

6
3 2 3 2 3 1

【样例输出2】

8

【样例说明】

【样例 1 解释】

当 Bessie 从唯一的一堆石子中取走 $4$、$5$、$6$ 或 $7$ 个石子时可以获胜。此时游戏会立刻结束。

【样例 2 解释】

当 Bessie 从任意一堆中取走 $2$ 或 $3$ 个石子时可以获胜。此后两头奶牛会交替取走相同数量的石子，而 Bessie 执行了最后一次操作。

【数据规模与约定】

测试点 3-5 满足 $N=2$。

测试点 6-10 满足 $N,a_i\le 100$。

测试点 11-20 没有额外限制。

【来源】

USACO 二月公开赛 Gold 组