Question:

I am having difficulty trying to solve the following problem:

<blockquote>

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.

</blockquote>

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 <a href="http://www.programmingwithbasics.com/2017/04/geeksforgeeks-solution-for-number-that.html" rel="nofollow">problem</a> 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 <a href="https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle" rel="nofollow">Inclusion-Exclusion principle</a> for some good understanding.

Good luck!

Here is an approach on how to handle this.

The place to start is to think about how you can split this into pieces. With such a problem, a place to start is the least common denominator (LCD) -- in this case 2,520 (the smallest number divisible by all the numbers less than 10).

The idea is that if x is not divisible by any number from 2-10, then x + 2,520 is also not divisible.

Hence, you can divide the problem into two pieces:

<ol><li>How many numbers between 1 and 2,520 are "relatively prime" to the numbers from 2-10?</li> <li>How many times does 2,520 go into your target number? You need to take the remainder into account as well.</li> </ol>