Inclusion-Exclusion implementation.

Revision en1, by symonsaroar, 2016-04-21 20:52:29

Problem:

A certain strange mathematician, Rasyak, considers a particular set of prime numbers beautiful. He also calls a composite number beautiful, if it is divisible by at least one prime number in his chosen set of beautiful primes. Given Rasyak’s set of M beautiful primes and an integer N, you have to find the number of beautiful numbers (both primes and composites) between 1 and N. For example, given a set of 2 beautiful primes, {2, 5}, there are 6 beautiful numbers between 1 and 10 (i.e. 2, 4, 5, 6, 8 and 10). Input The first line of the input gives the number of test cases, T (1 <= T <= 100). T test cases follow. Each will consist of one line containing a single integer M, followed by a line containing M space-separated prime numbers mi, followed by another line containing a single integer N. 1 <= M <= 25 1 <= mi <= 1000 1 <= N <= 2*10^9 Output For each test case, output one line containing a single integer X, where X is the number of beautiful numbers between 1 and N. Input 3 2 2 5 10 3 2 5 13 100 25 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 2000000000 Output 6 63 1759360857

I know this can be solved with inclusion-exclusion principle. But, How do I implement this.

please help me with implementing this in C/C++

It is already in this blog .. but it has only an answer saying about th inclusion-exclusion principle ..

Tags number theory, inclusion-exclusion, prime numbers

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English symonsaroar 2016-04-21 20:57:05 140 Tiny change: '**Input**_\n3\n2' -brbr (published)
en1 English symonsaroar 2016-04-21 20:52:29 1514 Initial revision (saved to drafts)