#PU1113. USACO 2021 February Contest, Gold — Problem 1. Stone Game
USACO 2021 February Contest, Gold — Problem 1. Stone Game
USACO 2021 February Contest, Gold — Problem 1. Stone Game
题目描述
Bessie and Elsie are playing a game with () piles of stones, where the -th pile has stones for each (). The two cows alternate turns, with Bessie going first. First, Bessie chooses some positive integer and removes stones from some pile with at least stones. Then Elsie chooses some positive integer such that divides and removes stones from some pile with at least stones. Then Bessie chooses some positive integer such that divides and removes stones from some pile with at least stones and so on. In general, , the number of stones removed on turn , must divide . The first cow who is unable to remove stones on her turn loses. Compute the number of ways Bessie can remove stones on her first turn in order to guarantee a win (meaning that there exists a strategy such that Bessie wins regardless of what choices Elsie makes). Two ways of removing stones are considered to be different if they remove a different number of stones or they remove stones from different piles.
输入格式
The first line contains . The second line contains space-separated integers .
输出格式
Print the number of ways Bessie can remove stones on her first turn in order to guarantee a win.
数据范围
Test cases 3-5 satisfy . Test cases 6-10 satisfy . Test cases 11-20 satisfy no additional constraints. Problem credits: Benjamin Qi
样例
样例 1
1
7
4
Bessie wins if she removes $4$, $5$, $6$, or $7$ stones from the only pile. Then
the game terminates immediately.
样例 2
6
3 2 3 2 3 1
8
Bessie wins if she removes $2$ or $3$ stones from any pile. Then the two players
will alternate turns removing the same number of stones, with Bessie making the
last move.