UVa 113

Basic formula but difficult constraints. The code I wrote was the first thought that came to my mind. I use binary search to correctly guess 'k' by using 1 to 10^9 as the range. This is my only Java submission, mainly because I did not have a pre-written BigInt class in C/C++. However later on I came across a neat mathematical way of doing it though I have not coded it yet. Here it is:

k^n = p

n*log(k) = log(p)

log(k) = log(p)/n

k = exp(log(p)/n)

My code is as follows:

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.math.BigInteger;







public class Main {




public static void main(String args[]) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String str1 = "", str2 = "";

int n = 0;

BigInteger p = new BigInteger("0");

while (true) {

str1 = br.readLine();

if (str1 == null) {

break;

}

n = Integer.parseInt(str1);

str2 = br.readLine();

if (str2 == null) {

break;

}

p = new BigInteger(str2);

double lo = 0, hi = 10e9;

while (lo <= hi) {

boolean flag = false;

double mid = lo / 2 + hi / 2;

BigInteger temp = new BigInteger(Integer.toString((int) mid));

temp = temp.pow(n);

int comp = temp.compareTo(p);

switch (comp) {

case 0:

flag = true;

System.out.println((int) mid);

break;

case 1:

hi = (int) mid - 1;

break;

case -1:

lo = (int) mid + 1;

break;

}

if (flag) {

break;

}

}

}

}

}