TopCoder

Thumb qz2vnqoblj6vp6q
miku
https://chino.taipei

User's AC Ratio

100.0% (12/12)

Submission's AC Ratio

48.6% (17/35)

Description

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

在最新的維修和更新程式之後,楓之谷又推出了最新的組隊任務!這次的組隊任務又更特別了!他們決定要讓玩家們多動一些頭腦,於是設計了這樣一個場景:每次任務有N個玩家闖關,每個玩家首先會得到一個以亂數指定的數字,範圍在0-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-9中的數字,中間以空白字元分隔,代表一開始已經依序排列好的玩家們各自拿到的數字。讀到N=M=0時代表檔案結尾,不需要對這筆資料作出任何輸出。

Output Format

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

Sample Input

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

Sample Output

2
4

Hints

Problem Source

原TIOJ1067 / NPSC2005初賽(prob C)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 65536