Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Killing Floor

By Shafin · Limits 1s, 512 MB

N(1N1018)N (1 \leq N \leq 10^{18}) robots have decided to take part on a battle royale. Every robot has a unique idid. The idid of the ithi^{th} robot (which we'll refer to as idiid_i from now on) is i2i^2. The strength of the ithi^{th} robot is Nidi\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 idid 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(1N1018)N (1 \leq N \leq 10^{18}) — the number of robots.


In the first line print an integer kk — the number of robots left after the battle.
In the next line print kk space separated integers — the idids of the remaining robots in increasing order.


1 4 9 16 36 

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

Output is huge. Use faster I/O



67% Solution Ratio

tasmeemrezaEarliest, Apr '20

theunownFastest, 0.1s

steinumLightest, 22 MB

steinumShortest, 352B


Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.