#U2021FG1. Stone Game

Stone Game

Bessie 和 Elsie 正在用 N1N105^5)堆石子进行一个游戏,其中对于每个 1iN,第 i 堆石子有 ai_i 个石子(1ai_i10**6^6**)。两头奶牛交替行动,Bessie 先手。

  • 首先,Bessie 选择某个正整数 s1_1 并从至少包含 s1_1 个石子的某堆石子中取走 s1_1 个石子。
  • 然后 Elsie 选择某个正整数 s2_2,使得 s1_1 整除 s2_2,并从至少包含 s2_2 个石子的某堆石子中取走 s2_2 个石子。
  • 然后 Bessie 选择某个正整数 s3_3,使得 s2_2 整除 s3_3,并从至少包含 s3_3 个石子的某堆石子中取走 s3_3 个石子,以此类推。
  • 总的来说,第 i 回合中取走的石子数量 si_i 必须整除 si_i+_+1_1

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

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

输入格式(从终端 / 标准输入读入):

输入的第一行包含 N。第二行包含 N 个空格分隔的整数 a1_1,…,aN_N

输出格式(输出至终端 / 标准输出):

输出可以令 Bessie 必胜(表示存在一种策略,无论 Elsie 如何行动,Bessie 均可获胜)的第一回合取石子的方法数。注意这个问题涉及到的整数大小可能需要使用 64 位整数型存储(例如,C/C++ 中的 long long)。

输入样例:

1
7

输出样例:

4

当 Bessie 从唯一的一堆石子中取走 4567 个石子时可以获胜。此时游戏会立刻结束。

输入样例:

6
3 2 3 2 3 1

输出样例:

8

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

测试点性质:

  • 测试点 3-5 满足 N=2
  • 测试点 6-10 满足 N,ai_i≤100,。
  • 测试点 11-20 没有额外限制。