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?

Answer1: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!

Answer2: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>