{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:25.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/9f663cd9d5b90509247c15ecc66c80ae?v\u003d1714825036\" alt\u003d\"/problems/enviousexponents/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003eAlice and Bob have an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e. Alice and Bob are not happy with\n their integer. Last night they went to a cocktail party and\n found that another couple had the exact same integer! Because\n of that they are getting a new integer.\u003c/p\u003e\n\n \u003cp\u003eBob wants to impress the other couple and therefore he\n thinks their new integer should be strictly larger than\n \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e.\u003c/p\u003e\n\n \u003cp\u003eAlice herself is actually fond of some specific integer\n \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e. Therefore, Alice\n thinks that whatever integer they pick, it should be possible\n to write it as a sum of \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e distinct powers of \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e.\u003c/p\u003e\n\n \u003cp\u003eBob is also a cheapskate, therefore he wants to spend as\n little money as possible. Since the cost of an integer is\n proportional to its size, he wants to get an integer that is as\n small as possible.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eA single line containing two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e, with \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq N \\leq 10^{18}$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq k \\leq\n 60$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e, the\n smallest integer larger than \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e that can be written as the sum of\n exactly \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e distinct\n powers of \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e12 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e17\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 3\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e31\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 4\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e182 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e193\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}