a994: 10325 - The Lottery
Tags :
Accepted rate : 43人/120人 ( 36% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 10:54

Content

孟加拉的運動聯盟最近在發行樂透(Lottery)時面臨一個問題,他們必須選擇一些號碼來作為這一期的號碼。但是要如何選呢?主席NondoDulal先生對歷史問題非常有興趣,他想要從其中想到解決的方法。你也許有興趣他如何得到解決的方法,最近他在讀 Joseph的問題。

有 N 張票,編號從 1 到 N。Nondo先生將隨意的選 M 個數,然後他將每張票上的數字分別去除這M個數字,只要有任一個可以整除,那這張票就被丟棄。到最後沒有被丟棄的票就被當成樂透的號碼。

例如:N=10, M=2, 且這2個數為 2,3。那麼最後留下來的票為 1, 5, 7 這3個數,因為2,3,4,6,8,9,10這7個數都至少被2或3其中之一整除。

你也知道,任何數除1一定可以整除,所以Nondo先生絕不會選 1 為這M個數其中之一。現在給你N,M以及這M個數,你必須算出最後留下來被當樂透的數有多少個。

Input
輸入含有多組測試資料。每組測試資料的第一列有 2 個正整數 N (10 <= N < 231)和 M ( 1 <= M <= 15)。接下來的一列有M個正整數(皆不大於N)。請參考 Sample Input。
Output
對每一組測試資料輸出一列,輸出最後留下來被當樂透的數有多少個。
Sample Input
10 2
2 3
20 2
2 4
100 3
3 5 7
Sample Output
3
10
45
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :
Lucky貓 ★★★  
Tags:
出處:
UVa10325 [管理者:
snail (蝸牛)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」