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.
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.
Input: 10 3 2 4 5 Output: 4
(The numbers 1, 3, 7 and 9 weren't cancelled).
recursive inclusion exclusion get WA in test 25.
ac at first go
mine giving wrong answer after 23rd test case don't know what to do
if you get a tle after test 23 you may want to check the gcd function
Last edit: 2020-02-22 19:49:31
I have WA in 25+ test.
where is segment tree in this problem? @linkret