NGM2 - Another Game With Numbers

题意翻译

## 题目描述 给出$K$个数$a_1,a_2,\cdots a_k$,求$[1,N]$中有多少个数不是这$K$个数中任意一个的倍数。 ## 输入格式 第一行是$N,K(1\leq N \leq 10^9,1 \leq K \leq 15)$ 第二行是$K$个数$a_1,a_2,\cdots a_k(a_i\leq 100)$ ## 输出格式 一行,表示$[1,N]$中所有不是任何一个$a_i$的倍数的数的个数。

题目描述

Little Chikoo likes to play with numbers. Often he plays the following game: 1. He chooses a number N and a set of positive integers. 2. He writes down all the numbers from 1 to N. 3. He chooses the first number (say x) from the set and cancels out all the multiples of x from 1 to N, including x. 4. He repeats step 3 for all the numbers from the set. One day Little Chikoo was in a mood to play pranks. So his brother asked him to play the game with a certain challenge. He made the game a little harder and asked him to find out the number of integers which aren't cancelled after he completes step 4. If he does that then Little Chikoo gets to play on his brother's Nintendo for one full day. Now Little Chikoo is in a hurry and wants to finish the job as soon as possible. He has asked for your help.

输入输出格式

输入格式


The first line of the input contains N and K. (N <= 10^9, K <= 15) Then K numbers follow all in a single line. All numbers are <= 100.

输出格式


The output file must contain the number of integers that aren't cancelled after he finishes step 4 of the game.

输入输出样例

输入样例 #1

10 3
2 4 5

输出样例 #1

4

说明

第一行n和k,表示接下来有k个数字,让你在1~n里面统计出不能被这k个数字中任意一个整除的数字个数,输出个数。 由 @TimeTraveller 提供翻译