#U2021FG1. Stone Game
Stone Game
Bessie 和 Elsie 正在用 N(1≤N≤10)堆石子进行一个游戏,其中对于每个 1≤i≤N,第 i 堆石子有 a 个石子(1≤a≤10****)。两头奶牛交替行动,Bessie 先手。
- 首先,Bessie 选择某个正整数 s 并从至少包含 s 个石子的某堆石子中取走 s 个石子。
- 然后 Elsie 选择某个正整数 s,使得 s 整除 s,并从至少包含 s 个石子的某堆石子中取走 s 个石子。
- 然后 Bessie 选择某个正整数 s,使得 s 整除 s,并从至少包含 s 个石子的某堆石子中取走 s 个石子,以此类推。
- 总的来说,第 i 回合中取走的石子数量 s 必须整除 s。
第一个无法在其回合中取走石子的奶牛为失败者。
计算可以令 Bessie 必胜(表示存在一种策略,无论 Elsie 如何行动,Bessie 均可获胜)的第一回合取石子的方法数。如果两种取石子的方法中取的石子数量不同或者取的石子堆不同,则认为是两种不同的取石子的方法。
输入格式(从终端 / 标准输入读入):
输入的第一行包含 N。第二行包含 N 个空格分隔的整数 a,…,a。
输出格式(输出至终端 / 标准输出):
输出可以令 Bessie 必胜(表示存在一种策略,无论 Elsie 如何行动,Bessie 均可获胜)的第一回合取石子的方法数。注意这个问题涉及到的整数大小可能需要使用 64 位整数型存储(例如,C/C++ 中的 long long)。
输入样例:
1
7
输出样例:
4
当 Bessie 从唯一的一堆石子中取走 4、5、6 或 7 个石子时可以获胜。此时游戏会立刻结束。
输入样例:
6
3 2 3 2 3 1
输出样例:
8
当 Bessie 从任意一堆中取走 2 或 3 个石子时可以获胜。此后两头奶牛会交替取走相同数量的石子,而 Bessie 执行了最后一次操作。
测试点性质:
- 测试点 3-5 满足 N=2。
- 测试点 6-10 满足 N,a≤100,。
- 测试点 11-20 没有额外限制。