Closest Power solution codechef

Closest Power solution codechef

An integer xx is said to be a Perfect Power if there exists positive integers aa and bb (i.e aa, and bb should be 1≥1) such that x=ab+1x=ab+1.

Given an integer nn, find the closest Perfect Power to nn. If there are multiple Perfect Powers equidistant from nn and as close as possible to nn, find the smallest one.

More formally, find the smallest integer xx such that xx is a Perfect Power and |nx||ny||n−x|≤|n−y| over all Perfect Powers yy.

Input Format Closest Power solution codechef

  • The first line of input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each test case contains a single integer nn.

Output Format

For each test case, print in a separate line, the smallest xx such that xx is a perfect power and |nx||n−x| is minimum.

Constraints Closest Power solution codechef

  • 1T1051≤T≤105
  • 1n10181≤n≤1018

Sample Input 1 

7
7
10
26
242
129
394857629456789876
353872815358409997

Sample Output 1  Closest Power solution codechef 

8
9
25
243
128
394857628993920400
353872815358410000

Explanation

Test case 11: n=7n=78=238=23 is a perfect power, but 66 is not, so the minimum difference obtainable is 11 when x=8x=8.

Test case 22: n=10n=109=329=32 is a perfect power, but 1111 is not, so the minimum difference obtainable is 11 when x=9x=9.

Test case 33: n=26n=2625=5225=52 is a perfect power, 27=3327=33 is also a perfect power. Both x=25x=25 and x=27x=27 give the minimum difference obtainable which is 11. The smallest of them is 2525.

Test case 44: n=242n=242243=35243=35 is a perfect power but 241241 is not, so the answer is 243243.

Test case 55: 128=27128=27 is closest to 129129.

Test case 66: 394857628993920400=6283769802394857628993920400=6283769802 is the closest to 394857629456789876394857629456789876.

Test case 77: 353872815358410000=243904353872815358410000=243904 is the closest to 353872815358409997353872815358409997.

Leave a Comment