Killing Floor

Shafin BDYP & Duoblogger Home Qu...
Limits 1s, 512 MB

$N (1 \leq N \leq 10^{18})$ robots have decided to take part on a battle royale. Every robot has a unique $id$. The $id$ of the $i^{th}$ robot (which we'll refer to as $id_i$ from now on) is $i^2$. The strength of the $i^{th}$ robot is $\big \lfloor \frac{N}{id_i} \big \rfloor $

Robots with the same strength have decided to fight among themselves. When two robots fight, the robot with lesser $id$ always wins, the other one disappears. The battle will continue as long as there are at least two robots with the same strength.

Your job is to find out how many robots will remain after the battle ends and which of them will remain.


The first and only line will contain an integer $N (1 \leq N \leq 10^{18})$ — the number of robots.


In the first line print an integer $k$ — the number of robots left after the battle.
In the next line print $k$ space separated integers — the $id$s of the remaining robots in increasing order.


1 4 9 16 36 

The $4^{th}$ and the $5^{th}$ robots have the same strength. Only the $4^{th}$ remained. Same goes for the $6^{th}$ to $25^{th}$ robots.

Output is huge. Use faster I/O


Login to submit.



67% Solution Ratio
tasmeemrezaEarliest, Apr '20
theunownFastest, 0.1s
steinumLightest, 22 MB
steinumShortest, 352B
Toph uses cookies. By continuing you agree to our Cookie Policy.