473. Droid formation
Time limit per test: 0.5
Memory limit: 262144
input: standardA long time ago (but somehow in the future), in a Galaxy Far Far Away...
— Your majesty, Jedi detachment almost finished to mine our new Death Cube! New battle droids are unable to restrain them! What to do!?
— Rest assured! What is the strength of every troop of droids?
— 12 droids, your majesty!
— Fools! I told you that a troop should have 4 variants of evolution but troop of 12 droids has 6! This perverts threads of the Power — and infeeds Jedis! Regroup the army — and Jedis will lose!
— Yes sir!
Number of variants of evolution of a troop of droids is the number of ways to draw it up in rows so that every row has the same number of droids. For example, a troop of 12 droids can be arranged in 1 row of 12 droids, 2 rows of 6 droids, 3 rows of 4 droids, 4 rows of 3 droids, 6 rows of 2 droids and 12 rows consisting of 1 droid each. So, as the Emperor noticed, there are 6 variants of evolution for this troop of droids.
You problem is more general — given the number K
of favorable variants of evolution, find the smallest positive size of a troop of droids N
which has this very number of variants of evolution.
Input file contains only number K
from the problem statement (1 ≤ K
Write to the output file the required number N
. If there is no such number, write to the output file number 0 instead.