TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

45.5% (5/11)

Description

  小蘋與阿谷在玩撿豆豆遊戲,盤面上有一群豆豆,小蘋與阿谷輪流從中拿出若干豆豆,每次可拿走的顆數是有限制的,直到一方無法再拿走豆豆的人輸,經過猜拳決定,這個遊戲將由小蘋先執行。
  比如說盤面上有五顆豆豆,每次每人一定要拿走 2 顆或 3 顆,此時如果小蘋拿走 2 顆,則阿谷必定拿走 3 顆,則小蘋因無法再執行任何動作而輸。如果小蘋拿走 3 顆,則阿谷必定拿走 2 顆,則小蘋也是輸。所以小蘋必輸無疑。又比如說盤面上有 5 顆豆豆,每次每人一定要拿走 3 顆或 4 顆,此時如果小蘋拿走 3 顆,盤面上只剩 2 顆,則阿谷無法再執行任何動作而輸。如果小蘋拿走 4 顆,盤面上只剩 1 顆,則阿谷也是輸。所以小蘋必贏無疑。
  聰明的小蘋發現,當一個遊戲中沒有隨機成分,且總會終止時,其中一方必定有必勝策略。於是她想要趁遊戲開始之前偷偷吃掉$x$顆豆子($x$不得超過盤面上的豆子總數),使得由小蘋先執行的時候永遠立於不敗之地。假設小蘋與阿谷都是絕頂聰明,請問她有幾種選擇非負整數$x$的方法呢?

Input Format

第一行有一個正整數$m$,表示盤面上有$m$顆豆豆。第二行有一個正整數$n$,後面接著$n$個以空白隔開的正整數$a_1, a_2, \cdots, a_n$,代表每次可以拿走的豆豆顆數。

子任務(測資) 額外限制 分數
1 (0~4) $m\leq 1000, n\leq 2, a_i\leq 10$ 20
2 (0~9) $m\leq 10^ 5,n\leq 5, a_i\leq 10^ 5$ 35
3 (0~14) $ m\leq 10^ 8, n\leq 10, a_i\leq 10^ 8$ 12
4 (15~22) $ m\leq 10^ {18}, n\leq 20, a_i\leq 20$ 33

Output Format

請輸出有幾種方式選擇非負整數$x$,使得小蘋可以獲得勝利。

Sample Input

#Sample Input 1
5
2 2 3
#Sample Input 2
6
2 1 6
#Sample Input 3
948794
7 9 48 79 487 879 4879 8794
#Sample Input 4
1000000000000000000
5 3 9 11 13 18

Sample Output

#Sample Output 1
3
#Sample Output 2
4
#Sample Output 3
565273
#Sample Output 4
761904761904761904

Hints

怪異的時限是模擬模考時的情況。

Problem Source

題目取自2017 TOI選訓第二次模擬考pA
Problem set by Yihda Yol

Subtasks

For Testdata: 0 ~ 4, Score: 20
For Testdata: 0 ~ 9, Score: 35
For Testdata: 0 ~ 14, Score: 12
For Testdata: 15 ~ 22, Score: 33
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 916 262144 65536
1 916 262144 65536
2 916 262144 65536
3 916 262144 65536
4 916 262144 65536
5 916 262144 65536
6 916 262144 65536
7 916 262144 65536
8 916 262144 65536
9 916 262144 65536
10 916 262144 65536
11 916 262144 65536
12 916 262144 65536
13 916 262144 65536
14 916 262144 65536
15 916 262144 65536
16 916 262144 65536
17 916 262144 65536
18 916 262144 65536
19 916 262144 65536
20 916 262144 65536
21 916 262144 65536
22 916 262144 65536