I am having difficulty trying to solve the following problem:
For Q queries, Q <= 1e6, where each query is a positive integer N, N <= 1e18, find the number of integers in [1,N] that cannot be divided by integers in [2,10] for each query.
I thought of using using a sieve method to filter out numbers in [1,1e18] for each query (similar to sieve of eratosthenes). However, the value of N could be very large. Hence, there is no way I could use this method. The most useful observation that I could make is that numbers ending with 0,2,4,5,6,8 are invalid. But that does not help me with this problem.
I saw a solution for a similar problem that uses a smaller number of queries (Q <= 200). But it doesn't work for this problem (and I don't understand that solution).
Could someone please advise me on how to solve this problem?
The only matter numbers in [2,10] are those primes which are 2, 3, 5, 7
So, Let say, the number cannot be divided by integers in [2,10] is the number cannot be divided by {2,3,5,7}
Which is also equalled to the total number between [1,n] minus all number that is divided by any combination of {2,3,5,7}.
So, this is the fun part: from [1,n] how many numbers that is divided by 2?
The answer is n/2 (why? simple, because every 2 number, there is one number divided by 2)
Similarly, how many numbers that is divided by 5? The answer is n/5
...
So, do we have our answer yet? No, as we found out that we have doubled count those numbers that divided by both {2, 5} or {2, 7} ..., so now, we need to minus them.
But wait, seems like we are double minus those that divided by {2,5,7} ... so we need to add it back
...
Keep doing this until all combinations are taken care of, so there should be 2^4 combination, which is 16 in total, pretty small to deal with.
Take a look at Inclusion-Exclusion principle for some good understanding.
Good luck!