Problem G
Yule Lads
The kids in Iceland are pretty lucky. Not only do they have one Santa Claus, but $N$ of them! They’re called the Yule Lads, and on each of the $N$ nights before Christmas, one of them comes to town, giving those that have been nice a small present, and those that have been naughty a potato.
On a street in a small town in Iceland, there are $N$ houses, numbered in turn from $1$ to $N$. Each house is beautifully decorated with Christmas lights, and initially they are all turned on.
On each of the $N$ nights before Christmas, one of the Yule Lads visits this street. The Yule Lad visiting $K$ nights before Christmas is very fond of the number $K$, and will only visit the houses whose house number is divisible1 by $K$. Furthermore, the Yule Lads are troublemakers, and will toggle the state of the Christmas lights on every house that they visit (i.e. turning the lights off if they are on, or turning them on if they are off).
However, some of the Yule Lads have been feeling sick, and did not come to town. On Christmas day all but the first house had their lights turned on. How many Yule Lads came to town?
Input
The first line of input contains a positive integer $N$, the number of Yule Lads and the number of houses in the street.
Output
Output a single integer, the number of Yule Lads that came to town. You can assume that there is only one scenario that leads to all houses having their lights on except for house number $1$.
Example
Consider the case $N = 6$. Then there are six Yule Lads, and six houses in the street. Here is what happens on each of the six nights before Christmas, assuming that no Yule Lad is sick.
-
Six nights before Christmas, the Yule Lad will turn the lights at house $6$ off.
-
Five nights before Christmas, the Yule Lad will turn the lights at house $5$ off.
-
Four nights before Christmas, the Yule Lad will turn the lights at house $4$ off.
-
Three nights before Christmas, the Yule Lad will turn the lights at house $3$ off, and the lights at house $6$ on.
-
Two nights before Christmas, the Yule Lad will turn the lights at houses $2$ and $6$ off, and the lights at house $4$ on.
-
The night before Christmas, the Yule Lad will turn the lights at houses $1$ and $4$ off, and the lights at houses $2$, $3$, $5$ and $6$ on.
However, house number $4$ has its lights off on Christmas day, contrary to what actually happened.
On the other hand, if only the Yule Lad that was supposed to come into town four days before Christmas is sick, then all lights, except for at house number $1$, will be lit on Christmas day. The correct answer is thus $5$: Yule Lads came to town $6$, $5$, $3$, $2$ and $1$ days before Christmas.
Grading
Your solution will be graded on a set of subtasks. A subtask will consist of multiple test cases. To get the points for a subtask, your solution must pass all test cases that are part of the subtask.
|
Subtask |
Score |
Constraints |
|
1 |
15 |
$N \leq 13$ |
|
2 |
10 |
$N \leq 1000$ |
|
3 |
12 |
$N \leq 10^5$ |
|
4 |
13 |
$N \leq 5 \cdot 10^{6}$ |
|
5 |
15 |
$N \leq 10^{8}$ |
|
6 |
14 |
$N \leq 10^{10}$ |
|
7 |
21 |
$N \leq 10^{13}$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
6 |
5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
13 |
9 |
| Sample Input 3 | Sample Output 3 |
|---|---|
68 |
42 |
Footnotes
- An integer $p$ is divisible by the integer $q$ if the division $p/q$ leaves no remainder.
