Stone Game

题目描述

Bessie 和 Elsie 正在玩一个游戏，有 $N$（$1\le N\le 10^5$）堆石子，其中第 $i$ 堆有 $a_i$ 个石子（对所有 $1\le i\le N$，$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 在第一回合为了保证获胜可以移走石子的方式数。

1
7

4

6
3 2 3 2 3 1

8

提示

注意：本题中涉及的整数可能很大，可能需要使用 64 位整数数据类型（例如 C/C++ 中的 "long long"）。 Bessie 若从唯一的一堆中移走 $4$、$5$、$6$ 或 $7$ 个石子则获胜。随后游戏立刻结束。 Bessie 若从任意一堆中移走 $2$ 或 $3$ 个石子则获胜。之后两名玩家将轮流移走相同数量的石子，且由 Bessie 做出最后一步。 计分： 测试点 3-5 满足 $N=2$。 测试点 6-10 满足 $N,a_i\le 100$。 测试点 11-20 无额外限制。 题目来源：Benjamin Qi

标签: USACO|2021|Gold

来源

USACO|2021|Gold