比赛场次 485
比赛名称 USACO水题大战
比赛状态 已结束比赛成绩
开始时间 2021-04-03 20:00:00
结束时间 2021-04-09 22:00:00
开放分组 全部用户
注释介绍 省选加油!
题目名称 Stone Game
输入输出 game.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 20 简单对比
用户 结果 时间 内存 得分

Stone Game

★★   输入文件:game.in   输出文件:game.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

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 组