0

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?

Donald
  • 1,300
  • 2
  • 13
  • 29

2 Answers2

3

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!

Pham Trung
  • 11,204
  • 2
  • 24
  • 43
  • +1 Thanks for explaining! I understand the code now. The TLE was because the code that I linked in my post was flushing the output on each query. – Donald Nov 15 '17 at 07:02
1

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:

  1. How many numbers between 1 and 2,520 are "relatively prime" to the numbers from 2-10?
  2. How many times does 2,520 go into your target number? You need to take the remainder into account as well.
Gordon Linoff
  • 1,242,037
  • 58
  • 646
  • 786
  • @user3386109 . . . I actually realize the optimizations that can be made on the problem. The idea was to give the OP an approach for solving it. – Gordon Linoff Nov 15 '17 at 03:19