95. 除法練習

0 Judge

Code: 0


\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

除法練習

題目敘述

Alice 跟 Bob 今天剛學到了除法跟質數的概念,他們知道一個數字是質數的意思就是那個數只有兩個因數,例如 $2, 3$ 都是質數,而 $1, 4$ 就不是質數。他們想要透過遊戲強加他們的反應,因此他們在桌子上寫下了 $N$ 個正整數,兩個人輪流選擇一個桌上的數字 $X_i$ ,再選擇一個可以整除那個數的質數 $p$,接著用那個質數 $p$ 去除 $X_i$。在同一回合中,只要還能夠整除,就可以除任意多次。沒有辦法動作的人就輸了。

舉個例子:一開始桌上有三個數字 $2,3,4$ ,Alice 選擇第三個數字 $X_3=4$ ,再選一個質數 $p=2$ ,接著用 $p$ 去除兩次,因此現在桌上的數字變成了 $2,3,1$。

一開始桌上有 $N$ 個數字,但是有一個數字被國防布蓋住了,因此只能看到其中的 $N-1$ 個數字,他們打算遊戲開始後再把布拿開,但已經知道那個數字不會大於 $M$ 。現在想要請問若 Alice 先開始,則有多少種狀況會使得 Bob 有必勝策略?

輸入說明

第一行有兩個正整數 $N, M$ 表示總共有 $N$ 個數字,被蓋住的數字不超過 $M$。 第二行有 $N-1$ 個正整數,代表沒有被蓋住的數字們,每個數字的大小不超過 $10^7$。

輸出說明

請輸出 Bob 有必勝策略的狀況數有幾種。

範例輸入1

3 3
1 2

範例輸出1

2

範例輸入2

4 3
4 3 1

範例輸出2

0

配分方法

  • 30% $1 \leq N \leq 100$, $1 \leq M \leq 1000$
  • 100% $1 \leq N \leq 10^6$, $1 \leq M \leq 10^7$

Hints

備註

第一個範例中,被蓋住的數字是 $2$ 或 $3$ 的話, Bob 有必勝的策略。

Judge Setting

run-time limit: 1000 ms
memory limit: 65536000 byte
測資數量: 0