TopCoder

i_am_noob
施~~廣~~霖~~

User's AC Ratio

88.1% (52/59)

Submission's AC Ratio

38.3% (85/222)

Tags

Description

楓之谷是一套網路遊戲,這個空虛的遊戲基本上就是不斷的打怪物、賺經驗值,學新的技能,和收集各種寶物。為了讓遊戲不要如此單調乏味,特別設計了一種東西叫做「任務」,任務的類型有著各種變化,例如跟某些人講話會觸發某些任務,然後就要去某些地方做某件事,收集到某些特定的東西等才能順利完成,簡單的講就是在沈悶的練功之中加入了一些劇情的元素,讓整個遊戲更有故事性和變化性。在各種任務之中,有一種特別的,本著「獨空虛不如眾空虛」精神而設的東西,稱為「組隊任務」,什麼是組隊任務呢?基本上就是讓多個玩家組成一個隊伍,然後以整個隊伍為單位共同配合共同行動,以溝通協調取代單打獨鬥,提供升級練功之外的另一種團隊樂趣。

在最新的維修和更新程式之後,楓之谷又推出了最新的組隊任務!這次的組隊任務又更特別了!他們決定要讓玩家們多動一些頭腦,於是設計了這樣一個場景:每次任務有 $N$ 個玩家闖關,每個玩家首先會得到一個以亂數指定的數字,範圍在 $0\sim 9$ 之間,然後讓他們依序站成一排直線,站定了之後就不能夠再調動彼此的次序,這時候每個人身上的數字連在一起就合成了一個新的數字,例如第一個人拿到 $4$,第二個人拿到 $1$,第三個人拿到 $6$,那麼我們得到的數字便是 $416$。現在任務的關主決定了一個數字 $M$,然後要求這些玩家之中的某些人出列,並且依照原本的次序形成另一個數字。比方說在上面的例子中,第一個人和第二個人出列便會得到 $41$ 這個數字,第一個人和第三個人出列便會得到 $46$ 這個數字,依此類推。如果說合成的新數字和 $M$ 互質,那麼這些出列的玩家便能通過考驗,進到下一個關卡去進行新的任務;如果失敗,那麼這些玩家便全部沒能通過這一關,任務就結束了。

現在問題來了,因為一開始的順序是不能改變的,所以我們不能再試圖調整該列玩家的順序,可是我們又希望能讓盡量多的玩家進到下一個關卡去,這個問題很困擾楓之谷的玩家們,你能寫一個程式來幫助這些頭痛的玩家,選出最多的人讓他們進到下一關嗎?
註:正整數 $m,n$ 互質的意思是他們的最大公因數為 $1$。

Input Format

整個測試檔包含多筆測試資料。每筆測試資料的第一行包含兩個以空白隔開的正整數 $N\ M ( 1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000)$,$N$ 代表這筆測試資料中有幾個玩家,$M$ 則代表關主指定的數字。每筆測試資料的第二行包含了 $N$ 個範圍在 $0\sim 9$ 中的數字,中間以空白字元分隔,代表一開始已經依序排列好的玩家們各自拿到的數字。讀到 $N=M=0$ 時代表檔案結尾,不需要對這筆資料作出任何輸出。

Output Format

對於每一筆測試檔中的測試資料,都必須有一行對應的輸出,行中只能有一個數字,代表能夠進到下一關的最大玩家數。

Sample Input 1

3 4
4 1 6
5 6
1 3 0 9 4
0 0

Sample Output 1

2
4

Hints

Problem Source

原 TIOJ1067 / NPSC2005 初賽 (prob C)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1