NGM2 - Another Game With Numbers


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.

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: 2022-12-03 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: 2020-12-01 23:49:56

recursive inclusion exclusion get WA in test 25.
use iterative code!

coolboy7: 2020-10-05 15:00:29

ac at first go

ak2783934: 2020-06-07 13:47:27

mine giving wrong answer after 23rd test case don't know what to do

ambuj2512: 2020-05-22 01:25:44

lcm(a,b)=(a*b)/gcd(a,b)
but
lcm(a,b,c)!=(a*b*c)/gcd(a,b,c)

s_hertelli: 2020-04-07 22:15:34

if you get a tle after test 23 you may want to check the gcd function
i had the same problem and my implementation of the gcd function was slow

abhinav_jain02: 2019-05-23 17:23:03

@Alexander
if you are computing lcm indirectly using hcf,then don't do so.
it cost me wrong answer on test case 25.
just pre calculate lcm for all possible subsets.
Ensure that you always use long long.
You don't need double datatype anywhere.

Alexander: 2019-04-09 09:09:42

I have WA in 25+ test.
I use long long int. My program gives me the maximum possible answer (10^9) in one of my own tests.
I coded program with true iterator as explained in the problem and I generated number of quite different tests - all passed.
I pass for K=1, and even K=0, for K=15
I pass for N=1 and N=10^9, and even for N=0.
for different groups of Ks: prime numbers, including one, repeating, dividing each other, have common dividers.
WHAT. THE. HACK!
I hate when I stuck this way :)

linkret: 2019-03-31 15:04:30

no

fabijanb: 2019-03-31 14:06:59

where is segment tree in this problem? @linkret


Added by:Paranoid Android
Date:2010-03-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:-