{"problem":{"name":"142. Hydra Tree","description":{"content":"You have a tree that is growing very fast. At first, the tree has one branch. On each successive day, the tree grows a certain number of branches. On each day, the number of new branches is calculated","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10269142"},"statements":[{"statement_type":"Markdown","content":"You have a tree that is growing very fast. At first, the tree has one branch. On each successive day, the tree grows a certain number of branches. On each day, the number of new branches is calculated as $n$ times $b$, where $b$ represents how many branches were on the tree on the previous day, and $n$ is a variable you have to calculate. $n$ will always be greater than one.\n\nAt an unknown number of days, the tree has $x$ branches. Given this value, figure out the minimum possible value of $n$ used in the formula, given that the tree started out with exactly one branch.\n\nThe only line of input contains a single positive integer $x$. $x$ will be less than 10000.\n\nOutput a single positive integer $n$: the minimum possible value of $n$, greater than one, such that the tree could have $x$ branches at some point. $n$ has to stay the same throughout the entire process of growing the tree, i.e. it cannot change between days.\n\n## Input\n\nThe only line of input contains a single positive integer $x$. $x$ will be less than 10000.\n\n## Output\n\nOutput a single positive integer $n$: the minimum possible value of $n$, greater than one, such that the tree could have $x$ branches at some point. $n$ has to stay the same throughout the entire process of growing the tree, i.e. it cannot change between days.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ x \\in \\mathbb{Z}^+ $ be the final number of branches, with $ x < 10000 $.  \nLet $ n \\in \\mathbb{Z} $ be the constant growth multiplier, $ n > 1 $.  \n\nThe tree starts with 1 branch.  \nOn day $ k $, the number of branches is $ b_k = n \\cdot b_{k-1} $, with $ b_0 = 1 $.  \nThus, after $ d $ days, $ b_d = n^d $, for some integer $ d \\geq 1 $.  \n\n**Constraints**  \n1. $ x = n^d $ for some integer $ d \\geq 1 $.  \n2. $ n > 1 $.  \n\n**Objective**  \nFind the minimum integer $ n > 1 $ such that $ x = n^d $ for some integer $ d \\geq 1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10269142","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}