NGM2  Another Game With Numbers
Little Chikoo likes to play with numbers. Often he plays the following game:
 He chooses a number N and a set of positive integers.
 He writes down all the numbers from 1 to N.
 He chooses the first number (say x) from the set and cancels out all the multiples of x from 1 to N, including x.
 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.
Input
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.
Output
The output file must contain the number of integers thatÂ aren't cancelledÂ after he finishes step 4 of the game.
Example
Input: 10 3 2 4 5 Output: 4
(The numbers 1, 3, 7 and 9 weren't cancelled).
hide comments
hit7sh:
20221203 15:30:33
consider the case which contains big distinct primes < 1e9, it will make the lcm to go huge... it wont even fit into 64 bit long, so handle it seperately, dont let the lcm grow too big. 

omar622:
20201201 23:49:56
recursive inclusion exclusion get WA in test 25.


coolboy7:
20201005 15:00:29
ac at first go 

ak2783934:
20200607 13:47:27
mine giving wrong answer after 23rd test case don't know what to do 

ambuj2512:
20200522 01:25:44
lcm(a,b)=(a*b)/gcd(a,b)


s_hertelli:
20200407 22:15:34
if you get a tle after test 23 you may want to check the gcd function


pedroslrey:
20200222 19:47:05
Last edit: 20200222 19:49:31 

abhinav_jain02:
20190523 17:23:03
@Alexander


Alexander:
20190409 09:09:42
I have WA in 25+ test.


linkret:
20190331 15:04:30
no 
Added by:  Paranoid Android 
Date:  20100309 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 VB.NET 
Resource:   