s5 (CCO Canadian_Computing_Competition_Senior)
Time limit: 1.5 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: set, number theory, graph theory, mathematical optimization

# Problem S5: The Filter

## Problem Description

Alice, the mathematician, likes to study real numbers that are between 0 and 1. Her favourite tool is the filter.

A filter covers part of the number line. When a number reaches a filter, two events can happen. If a number is not covered by the filter, the number will pass through. If a number is covered, the number will be removed.

Alice has infinitely many filters. Her first 3 filters look like this:

![](_page_0_Figure_5.jpeg)

In general, the $k$-th filter can be defined as follows:

*   Consider the number line from 0 to 1.
*   Split this number line into $3^k$ equal-sized pieces. There are $3^k + 1$ points and $3^k$ intervals.
*   The $k$-th filter consists of the $2$nd interval, $5$th interval, $8$th interval, and in general, the $(3i - 1)$th interval. The points are not part of the $k$-th filter.

Alice has instructions for constructing the Cantor set. Start with the number line from 0 to 1. Apply all filters on the number line and remove the numbers that are covered. The remaining numbers form the Cantor set.

Alice wants to research the Cantor set, and she came to you for help. Given an integer $N$, Alice would like to know which fractions $\frac{x}{N}$ are in the Cantor set.

## Input Specification

The first line contains the integer $N$.

The following table shows how the available 15 marks are distributed.

La version française figure à la suite de la version anglaise.

| Marks   | Bounds on $N$        | Additional Constraints |
| :------ | :------------------- | :----------------------- |
| 3 marks | $3 \le N \le 3^{18}$ | $N$ is a power of 3     |
| 4 marks | $2 \le N \le 10^5$   | None                    |
| 8 marks | $2 \le N \le 10^9$   | None                    |

## Output Specification

Output all integers $x$ where $0 \le x \le N$ and $\frac{x}{N}$ is in the Cantor set.

Output the answers in increasing order. The number of answers will not exceed $10^6$.

## Sample Input

```
12
```

## Sample Output

```
0
1
3
4
8
9
11
12
```

## Explanation of Output for Sample Input

Here is a diagram of the fractions and the first 4 filters. In reality, there are infinitely many filters.

![](_page_1_Figure_10.jpeg)

$\frac{5}{12}$, $\frac{6}{12}$ and $\frac{7}{12}$ are not in the Cantor set because they were covered by the 1st filter.

Furthermore, $\frac{2}{12}$ and $\frac{10}{12}$ are not in the Cantor set because they were covered by the 2nd filter.

It can be shown that the remaining fractions will pass through all filters.

La version française figure à la suite de la version anglaise.

Starter code:

Grader code:

Setup script:

Evaluation script: