# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Tejas Pandey

Tester: Nishank Suresh, Utkarsh Gupta

Editorialist: Pratiyush Mishra

# DIFFICULTY:

3115

# PREREQUISITES:

None

# PROBLEM:

A tuple of positive integers (a, b, c) is said to be a *bad tuple* if a, b, c are distinct, a divides b, and b divides c. For example, (1, 2, 4) and (7, 21, 42) are bad tuples while (1, 2, 3) and (2, 4, 4) are not.

Chef has the N integers from 1 to N with him. He wants to pick a subset of these numbers such that it doesnâ€™t contain a *bad tuple*. How many distinct subsets can he pick?

# EXPLANATION:

WLOG, we can assume in a tuple (a,b,c),\; a \leq b \leq c,

**Observation 1:** The numbers greater than \frac{N}{2} would not divide any other number and hence they can act only as c in the tuple.

**Observation 2:** Numbers greater than \lfloor \frac{N}{3} \rfloor can only divide 2 \times themselves so they can only be present in tuples of form (i, x, 2 \times x), where i is a divisor of x.

We will begin by finding all subsets not containing bad tuples consisting only of number from 1 to \lfloor \frac{N}{3} \rfloor. After finding such a tuple we will find pairs of numbers which have a divisor also present. Say numbers of form (i,y), where i divides y.

Now we will mark all multiples of such y greater than \lfloor \frac{N}{3} \rfloor as bad as including them in the subset would lead to formation of a bad tuple. After excluding such numbers it is easy to see by **Observation 2** that the tuples would be of the form of (i, x, 2 \times x), we can find all such x which would be paired with their twice. Hence finally we will have two types of numbers. One which have been paired and others which havenâ€™t.

The number which have been paired we can either include x or 2 \times x or none so we have three choices. For the numbers which havenâ€™t been paired we can either include the or exclude them so we have two choices. Hence the answer for this good subset would be:

The summation of all the answers of each good subset would be the final answer.

# TIME COMPLEXITY:

O(N \times 2^{\lfloor \frac{N}{3}\rfloor} )

# SOLUTION:

Setterâ€™s Solution

Tester1â€™s Solution

Tester2â€™s Solution