How do I implement Inclusion Exclusion to find number of multiples of k numbers in a given range?

general
,
1

This is related to the following problem from the ico- http://www.iarcs.org.in/inoi/contests/sep2004/Advanced-2.php

It is a simple problem that requires you to use inclusion-exclusion to find number of multiples of k numbers from 1 to n.
My question is how do I compute lcm of elements of all possible subsets of the given set.(Refer to solution here- http://www.iarcs.org.in/inoi/contests/sep2004/Advanced-2-solution.php)
Some pseudo-code will be helpful.

2 Likes
2

You can find a detailed explanation of this problem at this link :

Leaf Eaters

Happy Coding !

3

I’ve posted the same link in my question. My doubt is how do I implement the last part, which is computing lcm of elements of all possible subsets.

1 Like
4

Using bitmasks !!

My solution : http://paste.ubuntu.com/9713177/

1 Like
5

You can do it using recursion: http://paste.ubuntu.com/9713626/

1 Like
6

@superty Sorry for bothering you, is it possible for you to explain your find() function?

7

Each call of find considers a certain subset of the lengths.

depth is actually the number of lengths in the current subset.

cur is the lcm of all the lengths in the current subset.

start is the index of the last length in the current subset.

let num = ceil(N/cur) = number of leaves eaten by a caterpillar of length cur

(N is actually one minus the N given in input because I want to index leaves from 0)

For each subset, if the number of lengths in the subset is even, we need to subtract num, and if it’s odd we add num. Also if the number of elements is zero we don’t add anything.

8

To create each possible subset, we add every length from L[start + 1] to L[K] to the subset and call find again. (we don’t add all of them, for each call only one is added)

How do we do this? Suppose we wish to add L[i] to the subset.

Then the call to find must be find(i, lcm(cur, L[i]), depth + 1)