1.

import java.util.Scanner;

/**
* Angewandte Mathematik, SS11
* Problem: 10622 Perfect P-th Powers
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1563
*
* @author Benedikt Z¨nnchen
* @author Erik Wenzel
* @version 1.0, 06/04/2011
*
* Method : Merken des letzten maximalen Teilers. Der daraufolgende muss gleich oder ein vielfaches des vorigen
* Teilers sein. zb 2*2*2*3 * 2*2*2*3 => 2 ist 6mal drin, 3 ist 2 mal drin ggT(6,2) = 2 => gr¨§te Potenz = 2.
* Bei ungeraden Zahlen muss au§erdem darauf geachtet werden das der ggT ungerade ist!
* Status : Accepted
* Runtime: 0.140
*/

public class Main
{

public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
long number;

while(sc.hasNext() && (number = sc.nextLong()) != 0)
{
if(number == 0 || number == 1 || number == -1)
{
System.out.println(1);
}
else
{
System.out.println(getMaxP(number));
}
}
}

/**
* Gibt die gr¨§t m¨gliche Potenz einer Potenzdarstellung der Zahl zur¾ck
* @param n ganze Zahl
* @return gr¨§te Potenz
*/
public static int getMaxP(long n)
{
boolean found = false;
boolean neg = false;
int lastMaxP = 0;
int currentMaxP = 0;

if(n < 0)
{
n = Math.abs(n);
neg = true;
}

for(int i = 2; i <= n; i++)
{
if(!found && i > Math.sqrt(n))
{
return 1;
}
else if(n%i == 0)
{
found = true;
currentMaxP=1;
n = n/i;
while(n%i == 0)
{
n = n/i;
currentMaxP++;
}

if(lastMaxP == 0)
{
lastMaxP = currentMaxP;
}

if(currentMaxP != lastMaxP && (currentMaxP=ggT(currentMaxP, lastMaxP)) == 1)
{
return 1;
}
else
{
if(neg)
{
while(currentMaxP%2==0)
{
currentMaxP = ggT(currentMaxP, currentMaxP/2);
}
}
lastMaxP = currentMaxP;
}
}
}

return currentMaxP;
}

/**
* Euklids Algorithmus zur bestimmung des gr¨§ten gemeinsamen
* Teilers
* @param a ganze Zahl
* @param b ganze Zahl
* @return gr¨§ter gemeinsamer Teiler
*/
public static int ggT(int a, int b)
{
int r = -1;

while(r!=0)
{
r = a%b;
a = b;
b = r;
}

return a;
}
}

2.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/**
* Angewandte Mathematik, SS11
* Problem: 10622 Perfect p-th Power
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1563
*
* @author Fabian Trampusch
* @author Robert Schwarz
* @version 1.0, 04/10/2011
*
* Status : Wrong Answer
* Runtime: 0.000
*/

public class Main {
static int getGcd(int x, int y) {
int t, k = 0;

while ((x & 1) == 0 && (y & 1) == 0) {
x = x >> 1;
y = y >> 1;
k++;
}

if ((x & 1) == 1)
t = -y;
else
t = x;

while (t != 0) {
while ((t & 1) == 0) {
t = t >> 1;
}

if (t > 0)
x = t;
else
y = -t;

t = x - y;
}

return x * (int) Math.pow(2, k);
}

static private List<Integer[]> getPrimeFactors(int val) {
val = Math.abs(val);
int sqrtVal = (int) Math.sqrt(val) + 1;
List<Integer[]> pf = new ArrayList<Integer[]>();

int p = 0;
while (val % 2 == 0 && val > 1) {
val /= 2;
p++;
}

if (p > 0) {
pf.add(new Integer[] { 2, p });
}

for (int prime = 3; prime <= sqrtVal && val > 1; prime += 2) {
p = 0;
while (val % prime == 0 && val > 1) {
val /= prime;
p++;
}
if (p > 0) {
pf.add(new Integer[] { prime, p });
}
}

if (val != 1)
pf.add(new Integer[] { val, 1 });

return pf;
}

public static void main(String[] args) throws Exception {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(
System.in));

while (true) {
String input = br.readLine();
int power = 0;

if (input.equals("0"))
break;
else {
int val = Integer.parseInt(input);
boolean negative = val < 0;

List<Integer[]> primeFactors = getPrimeFactors(val);

if (primeFactors.size() > 1) {
int gcd = 1;
for (int i = 0; i < primeFactors.size() - 1; i++) {
int newGcd = getGcd((int) Math.pow(
primeFactors.get(i)[0],
primeFactors.get(i)[1]), (int) Math.pow(
primeFactors.get(i + 1)[0],
primeFactors.get(i + 1)[1]));

if (newGcd > gcd)
gcd = newGcd;
}

if (gcd == 1)
power = 1;
else {
while (val % gcd == 0 && val > 1) {
val /= gcd;
power++;
}
}
} else {
if (negative) {
while (primeFactors.get(0)[1] % 2 == 0) {
primeFactors.get(0)[1] /= 2;
}
}

power = primeFactors.get(0)[1];
}

System.out.println(power);
}
}
} catch (Exception e) {
}
}
}

3.

/**
 * Angewandte Mathematik, SS11
 * Problem: 10622 Perfect P-th Powers
 * Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2113
 *
 * @author Westerfield, Christopher
 * @author Gent Selmanaj
 * @author Marco Schuster
 * @version 1.0, 03/21/2011
 *
 * Method : Ad-Hoc
 * Status : Accepted
 * Runtime: 0.140
 */
import java.util.*;
import java.io.*;

class Main {

public static void main(String[] args) throws Exception {
Map<Integer, Set<Long>> powers = new HashMap<Integer, Set<Long>>();

for (int i = 2; i <= 31; i += 1)
powers.put(i, new HashSet<Long>());

for (int n = 2; n <= (int) Math.sqrt(Integer.MAX_VALUE) + 1; n += 1) {
int counter = 2;
for (long i = n * n; i <= 2147483648L; i *= n) {
powers.get(counter).add(i);
counter += 1;
}
}

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder resultString = new StringBuilder();
long n = Long.parseLong(reader.readLine().trim());

while (n != 0) {

long abs = Math.abs(n);
boolean minus = n < 0;

int maxKey = 1;
for (int key : powers.keySet()) {
if (minus && key % 2 == 0) {
continue;
}
if (powers.get(key).contains(abs)) {
maxKey = Math.max(key, maxKey);
}
}

resultString.append(maxKey);
resultString.append("\n");

n = Long.parseLong(reader.readLine().trim());
}

reader.close();

System.out.print(resultString);
}
}

4.

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
* Angewandte Mathematik, SS11
* Problem: 10622 - Perfect P-th Powers
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1563
*
* @author Unverzart Michael
* @author Wurth Manuel
* @version 1.0, 3/4/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.340
*/

public class Main {
public static void main(String[] args) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String inputLine;
while((inputLine = reader.readLine()) != null) {
long n1 = new Long(inputLine.trim());
long n2 = Math.abs(n1);
if (n1==0) break;
boolean print = false;
for(int basis = 2; basis <= Math.sqrt(n2); basis++) {
double wert = 0f;
int exponent = 1;
do{
exponent++;
wert = Math.pow(basis, exponent);
if(wert == n2){
if(n1>0){
System.out.println(exponent);
print = true;
break;
} else if((exponent%2)==1) {
System.out.println(exponent);
print = true;
break;
}
}
}while(wert < n2);
if(print) break;
}
if(!print){
System.out.println(1);
}
}
}
}

5.

/**
* Angewandte Mathematik, SS11
* Problem: 10622 Perfect P-th Powers
* Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2113
*
* @author Schramm, Felix
* @author Vogel, Johannes
* @version 1.0, 04/11/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.200
*/


import java.math.*;
import java.util.Scanner;

public class Main {
public static void main (String args[]) {

Scanner input = new Scanner(System.in);
while(input.hasNextInt()){
int number = input.nextInt();
int max = 1;
if (number == 0)
break;
if(!(number==1||number==-1)){ // Sqrt und cbrt für 1 und -1 gibt ganze Zahl.
double root = Math.sqrt(number);
max=Math.floor(root)==root?2:1;
root = Math.cbrt(number);
max=Math.floor(root)==root?3:max;
int maxP = gievMaxPower(number, (int)root);
max=Math.max(max, maxP);
}
System.out.println(max);
}
}

private static int gievMaxPower(int number, int cap) {
if(number==-2147483648) // Min Int kennt kein positives Pendant!!!111einseinself.
return 31;
boolean neg = number<0;
number=Math.abs(number);
cap=Math.abs(cap);
int init = number%2==0?2:3; // Gerade Zahlen haben gerade Basen,
ungerade ungerade.
for(int base=init;base<=cap;base+=2){ // Basen bis zur dritten
Wurzel der Zahl werden getestet.
int power = 2;
long powered = 0;
do{ // Exponent wird erhöht, bis Potenz größer als die Zahl.
powered = (long)Math.pow(base, power);
if(powered==number&&!(neg&&power%2==0))
return power;
power++;
}while(powered<number);
}
return 1;
}
}

6.

/**
* Angewandte Mathematik, SS11
* Problem: 10622-Perfect Pth-Power
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1563
*
* @author Wolff, Marco
* @author Weber, Christian
* @author Waldleitner, Christoph
* @version 1.0, 04/12/2011
*
* Method : brute force
* Status : Accepted
* Runtime: 0.156
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
public static void main(String[] args) {
int number = 0, copiedNum = 0, currentGCD = 0, allEmpty = 0;
int[] myPrimes = getPrimes(), myPowers = new int[myPrimes.length];

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = "", totalInput = "";
StringTokenizer parseNumbers;

while(!input.equals("0")) {
try {
input = br.readLine();
}
catch(IOException e) {}

if(!input.equals("0"))
totalInput += input + " ";
}

parseNumbers = new StringTokenizer(totalInput);

while(parseNumbers.hasMoreTokens()) {
number = Integer.parseInt(parseNumbers.nextToken());
copiedNum = number;

if(number > 1 || number < -1) {
allEmpty = 0;

for(int i = 0; i < myPrimes.length; i++) {
while(copiedNum % myPrimes[i] == 0) {
myPowers[i]++;
copiedNum /= myPrimes[i];
if(copiedNum / myPrimes[i] == 0)
break;
}
copiedNum = number;
}

currentGCD = myPowers[0];

for(int i = 0; i < myPowers.length; i++) {
allEmpty += myPowers[i];
if(myPowers[i] != 0) {
currentGCD = GCD(currentGCD, myPowers[i]);
myPowers[i] = 0;
}
}

if(allEmpty == 0)
currentGCD = 1;

if(number < 0) {
while(currentGCD % 2 == 0)
currentGCD /= 2;
}

System.out.println(currentGCD);
}
}

System.exit(0);
}

static int[] getPrimes() {
int limit = (int)Math.sqrt(Integer.MAX_VALUE) + 1, numberOfPrimes = 0;
int[] primeArray, primes = new int[limit];

boolean[] notPrime = new boolean[limit];

for(int i=2; i<limit; i+=2) {
if(notPrime[i])
continue;
primes[numberOfPrimes++] = i;

for(int j=i; j<limit; j+=i) {
notPrime[j] = true;
}
if(i==2)
i--;
}

primeArray = new int[numberOfPrimes];
System.arraycopy(primes, 0, primeArray, 0, numberOfPrimes);

return primeArray;
}

static int GCD(int a, int b) {
int helper;
if(b > a)
GCD(b,a);
if(b == 0)
b = a;
else {
helper = a % b;

while(helper > 0) {
a = b;
b = helper;
helper = a%b;
}
}
return b;
}
}

7.

import java.io.*;
import java.util.StringTokenizer;


/**
* Angewandte Mathematik, SS11
* Problem: 10622 - Perfect P-th Powers
* http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1563* @author Sebastian Stumpf
* @author Benjamin Vogt
* @version 1.0, 2011-04-12 10:23:27
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.244
*/

public class Main
{
public static void main(String args[])
{
/*
long start = System.currentTimeMillis();
StringBuilder sb = new StringBuilder("");
for(int i=1; i<=1000; i++)
{
sb = sb.append(i+"\n");
}
sb.append("0");
String s = sb.toString();
try{
InputStream is = new ByteArrayInputStream(s.getBytes("UTF-8"));
*/
try{
//Buffered reader ist nochmal um einiges schneller als Scanner!
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(input.readLine());
long number;
while((number = Integer.parseInt(tokenizer.nextToken())) != 0)
{
boolean positive = number > 0? true: false;
number = Math.abs(number);
long max = (long)Math.sqrt(number);
boolean notFound = true;
for(long basis = 2; basis <= max; ++basis)
{
//Berechnet den logarithmus von number zur basis b. wenn dieser
//ganzzahlig gerundet == der Number selbst ist, dann ist number
//als basis^power darstellbar
//der erste Fund muss zugleich der größte sein, da mit minimaler
//basis derexponent maximal ist!
long power = Math.round(Math.log(number)/Math.log(basis));
if(number == Math.pow(basis, power))
{
if(positive)
{
System.out.println(power);
notFound = false;
break;
}
//bei negativen zahlen werden nur ungerade powers akzeptiert
if(!positive && power % 2 != 0)
{
System.out.println(power);
notFound = false;
break;
}
}
}
if(notFound)
System.out.println(1);


tokenizer = new StringTokenizer(input.readLine());
}
}catch(Exception e){}
/*
}
catch (UnsupportedEncodingException e)
{
e.printStackTrace();
}
System.out.println(System.currentTimeMillis() - start);
*/
}
}

8.

/**
* Angewandte Mathematik, SS11
* Problem: 10622 Perfect P-th Powers
* Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_pro
blem&problem=1563
* @author Brielbeck, Daniel
* @author Weber, Georg
* @version 1.0, 04/10/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.104
*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String input;
while ((input = reader.readLine()) != null) {
if (input.equals("0"))
break;
Long inti = Long.valueOf(input);
if (inti == 1 || inti == -1) {
System.out.println(1);
break;
}
if (inti >= Integer.MIN_VALUE && inti <= Integer.MAX_VALUE) {
// bei plus
if (inti > 0) {
for (int i = 31; i >= 0; i--) {
if ((Math.abs((Math.pow(inti, 1 / (double) i) - (Math
.round(Math.pow(inti, 1 / (double) i)))))) < 0.000000000001) {
System.out.print(i);
System.out.print("\n");
break;
}
}
} else {
// bei minus:
for (int i = 31; i >= 0; i = i - 2) {
inti = Math.abs(inti);
if ((Math.abs((Math.pow(inti, 1 / (double) i) - (Math
.round(Math.pow(inti, 1 / (double) i)))))) < 0.000000000001) {
System.out.print(i);
System.out.print("\n");
break;
}
}
}
}
}
}
}


9.

/**
 * Angewandte Mathematik, SS11 
 * Problem: 10622 Perfect P-th Powers
 * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1563
 * 
 * @author Florian Stein 
 * @author Franz Sommer
 * @version 1.1, 04/11/2011
 * 
 * Method : Brood Force
 * Status : Accepted
 * Runtime: 0.204
 * Lessons learned: Data Type conformity, or: The Question of casting or not casting?
 *     Usage of higher data types to overcome problem limitations.
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{

public static void main(String[] args) throws IOException
{   BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    long x;
    while(true)
            {
                String l = reader.readLine(); 
                
                if(l == nullbreak;
                x = Long.parseLong(l);
                if(x == 0) break;
                 System.out.println(pthpower(x));
            }
    }


public static long pthpower(long x)
{
double p = 1;
int s = x<0 ? -1:1;
x = x * s;
double logx = Math.log((double)x);
double sqrtx = (int)Math.sqrt((double)x);
for(int b=2;b<=sqrtx; b++)
{ p = Math.round( logx / Math.log(b) );
if(Math.pow(b, p) == x)
{
if(s==-1)
{
while(p%2==0) p/=2;                    
}
return (long)p;
}
}
return 1;
}

}

10.

/**
* Angewandte Mathematik, SS11
* Problem: 10622 Perfect P-th Powers
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1563
*
* @author Ritter Marius
* @author Wende Tom
* @author Zehentbauer Stefan
* @version 1.0, 10/23/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.184
*/

import java.util.Scanner;

public class Main {

/**Rechnet eine Zahl i hoch einer zahl p.
* @param i int
* @param p int
* @return sum long, i hoch p*/
long powerup(int i, int p){
long sum = i;
for(int j = 2; j <= p; j++){
sum = sum * i;
}
return sum;
}

public static void main(String[] args){
Scanner scr = new Scanner(System.in);
long x = scr.nextLong();
while(x != 0){
//Schalter ob eine Zahl gefunden wurde
boolean found = false;
int length;
//Falls die Zahl negativ ist...
if(x < 0){
length = (int)Math.sqrt(-1 * x);
for(int i = -2; i >= -length; i--){
long ans = i;
int p = 2;
while(ans > x){
ans = new Main().powerup(i, p);
p++;
}
if(ans == x){
System.out.println(p-1);
found = true;
break;
}
}
if(!found){
System.out.println(1);
}
//...oder positiv
}else{
length = (int)Math.sqrt(x);
for(int i = 2; i <= length; i++){
long ans = i;
int p = 2;
while(ans < x){
ans = new Main().powerup(i, p);
p++;
}
if(ans == x){
System.out.println(p-1);
found = true;
break;
}
}
if(!found){
System.out.println(1);
}
}
x = scr.nextLong();
}
}
}

-----------------------------------------------------------------

1.

/*
* ACM Contest training
* Problem: 10622 - Perfect P-th Powers
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1563
*
* @author Christoph Goettschkes
* @version 1.0, 10/27/2010
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.148
*/

import java.util.*;
import java.io.*;

class Main {

public static void main(String[] args) throws Exception {
Map<Integer, Set<Long>> powers = new HashMap<Integer, Set<Long>>();

for (int i = 2; i <= 31; i += 1)
powers.put(i, new HashSet<Long>());

for (int n = 2; n <= (int) Math.sqrt(Integer.MAX_VALUE) + 1; n += 1) {
int counter = 2;
for (long i = n * n; i <= 2147483648L; i *= n) {
powers.get(counter).add(i);
counter += 1;
}
}

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder resultString = new StringBuilder();
long n = Long.parseLong(reader.readLine().trim());

while (n != 0) {

long abs = Math.abs(n);
boolean minus = n < 0;

int maxKey = 1;
for (int key : powers.keySet()) {
if (minus && key % 2 == 0) {
continue;
}
if (powers.get(key).contains(abs)) {
maxKey = Math.max(key, maxKey);
}
}

resultString.append(maxKey);
resultString.append("\n");

n = Long.parseLong(reader.readLine().trim());
}

reader.close();

System.out.print(resultString);
}
}





2.
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 10622 - Perfect P-th Powers
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=9
*
* @author Evgeni Pavlidis
* @version 1.0, 06/19/2010
*
* Method : precalculation
* Status : Accepted
* Runtime: 0.332
*/

import java.io.*;
import java.util.*;

class Main
{
private static Map<Integer, Integer> pPower = new HashMap<Integer, Integer>();

public static void main(String...args)
{
Scanner sc = new Scanner(System.in);
int x, n, p;

int squareRoot = (int)Math.sqrt(Integer.MAX_VALUE);
for(int i = 2; i <= squareRoot; i++)
for(n = i*i, p = 2; n > 0 && n < Integer.MAX_VALUE; n *= i, p++)
{
if(!pPower.containsKey(n))
pPower.put(n, p);

if(p % 2 == 1 && !pPower.containsKey(-n))
pPower.put(-n, p);
}

pPower.put(Integer.MIN_VALUE, 31);

while((x = sc.nextInt()) != 0)
if(pPower.containsKey(x))
System.out.println(pPower.get(x));
else
System.out.println(1);
}

}


3.

package acm_10622_perfect_pth_powers;

/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: 10622 Perfect p-th powers
* Link: http://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=63&page=show_problem&problem=1563
*
* @author Martin Lambeck
* @version 1.0, 01/08/2010
*
* Method : simple math
* Status : Accepted
* Runtime: 0.120
*/

public class Main
{
final static double EPSILON = 0.00005;
final static double LOG2 = Math.log(2);

static BufferedIntReader r = new BufferedIntReader();


public static void main(String...args)
{
while (testcase());
}

public static boolean testcase()
{
int x = r.nextInt();
int p;

if (x == 0)
return false; //end of input



//upper bound for p: x=2^p <=> p=log2(x)


//special case:
//x = -2^31 = -2147483648
//int cannot hold abs(-2^31) !!!
if (x == -2147483648)
{
System.out.println("31");
return true;
}

p = (int)(Math.log(Math.abs(x))/LOG2 + 1);


while (true)
{
double b;
double pow;

b = Math.pow(Math.abs(x), 1.0/p); // b = p-th root of x = x^(1/p)

if (x < 0) //if x negative, negate b
b = -b;

b = Math.round(b); // b <- [b]

pow = Math.pow(b, p); //pow = [(x^(1/p))]^p = [b]^p

//(b^p = [b]^p) ?
if (approx(pow, x))
{
System.out.println(p);
break;
}

p--;
}

return true;
}

public static boolean approx(double d, int i)
{
return (Math.abs(d - i) <= EPSILON);
}

}


class BufferedIntReader
{
byte[] buf = new byte[1024*32];
int pos = 0;
int len = 0;

public int nextInt()
{
int num = 0;
int chr;
boolean found = false;
boolean negative = false;
boolean stop = false;

while (!stop)
{
if (pos == len)
{
pos = 0;

try
{
len = System.in.read(buf);

} catch (java.io.IOException e)
{
throw new IllegalStateException(e); //wrap into runtime exception and throw
}
}

if (len == -1)
{
if (!found)
throw new IllegalStateException(new java.io.EOFException());

stop = true;
chr = ' ';

} else
{
chr = buf[pos];
pos++;
}

if (chr >= '0' && chr <= '9')
{
num = num*10 + (chr - '0');
found = true;

} else if (chr == '-')
{
if (found)
{
// - after a number
// stop here, and push back - into the buffer, maybe sign of next number
stop = true;
pos--;
buf[pos] = '-';

} else
{
negative = true;
}

} else
{
if (found)
stop = true;
else
negative = false;
}
}

return (negative ? -num : num);
}
}

4.

/**
 * Angewandte Mathematik, SS09, IFB 2C
 * ACM Problem #10622 - Perfect P-th Powers
 *
Link:
http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1563
 *
 * @author Mohr
 * @author Schirm
 * @author Mathauser
 * @version 1.0, 04/06/2009
 *
 * Status : Accepted
 * Runtime: 0.380
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
    
    
    public static long pth(long zahl){
        
        double logZahl;
        
        int sign = zahl<0 ? -1 : 1;
        zahl *= sign;
        
        double  sqrt = Math.sqrt((double)zahl);
        logZahl = Math.log((double)zahl);
        
        for(int b = 2; b <= sqrt; b++)    {
            
            double p = Math.round(logZahl / Math.log(b));
            
            if(Math.pow(b,p) == zahl){
                
                if(sign==-1){
                    while(p%2==0) p/=2;                    
                }
            
                return (long)p;
            }
        }
        
        return 1;
    }
    
        public static void main (String... args) throws IOException    {
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            while(true)
            {
                String line = reader.readLine();
                
                if(line == null)
                     break;
                long buf = Long.parseLong(line);
                if(buf == 0)
                    break;
                
                System.out.println(pth(buf));
            }
    }
}



5.


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #371 (Perfect P-th Powers)
* Link: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1563
*
* @author Doina Logofatu
* @author Christian Posselt
* @author Jonathan Schubert
*
*
* @version 1.1, 04/06/2009
*
* Status : Accepted
* Runtime: 0.200
*/
import java.io.BufferedInputStream;
import java.io.PrintWriter;
import java.util.Scanner;


class Main
{
public static void main(String[] args)
{
BufferedInputStream bin = new BufferedInputStream(System.in);
PrintWriter w = new PrintWriter(System.out);
Scanner s = new Scanner(bin);

long n;

while(s.hasNextLong() && (n=s.nextLong())!=0 )
{
System.out.println(facts(n));
}
w.flush(); //flush the writer
}
public static long facts(long x)
{
//Call signum x
int sign = x<0?-1:1;
if(x<0)
x *= -1;
int p = 0;
long j;
//get amount of factor 2
while(x % 2 == 0)
{
x /= 2;
p++;
}

//get amount of factor j
for(j=3; x!=1 && p==0 && j*j<=x; j+=2)
{
if(x%j == 0)
{
while(x % j == 0)
{
p++;
x/=j;
}
break;
}
}
//testnumber is prim. GGT must be one
if(p == 0)
return 1;
//Calculate the ggT of exponents
for(;x != 1 && p != 1 && j*j <= x; j += 2)
{
if(x%j == 0)
{
int t = 0;
while (x%j == 0)
{
t ++;
x /= j;
}
p = GCD(p,t);
}
}

if(x > 1)
return 1;
//if testdigit is negative. calculate (a^m)^n
if(sign < 0)
{
while(p%2 == 0)
p /= 2;
return p;
}
return p;
}

public static int GCD(int a,int b)
{
while (a!=b)
{
if (a>b)
a -= b;
else
b -= a;
}
return a;
}
}


6.

/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem
* Link: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1563
*
* @author Miesel Christoph
* @author Seilbeck Robert
* @author Wolfram Andre
* @version 1.0, 04/20/2009
*
* Status : Accepted
* Runtime: 0.440
*/

import java.util.*;

public class PerfectP
{
/* Schnelles Potenzieren:

long long pow(int n, int p){
long long res;
if(p==0) return 1;
if(p==1) return n;
if(p%2==0){
res = pow(n, p/2);
return res*res;
}
return n*pow(n, p-1);
}
*/

/*
x=b^p <=> log x = p log b <=>
p=(log x/log b)

Brute Force - Suche nach dem erst möglichen
Paar (b, p) - b wie klein wie möglich => p maximal

für negatives x darf p nur ungerade sein!

wir vewenden in Formel log((double)x)/log((double)b)+0.5;
die equivalent mit round(log((double)x)/log((double)b))
weil round() in ANSI C nicht vorhanden

Kritische Testcases: 14348907->15, -2147483648->31
*/

long pow(int n, int p)
{
long res;
if(p==0) return 1;
if(p==1) return n;
if(p%2 == 0)
{
res = pow(n,p/2);
return res*res;
}
return n*pow(n,p-1);
}
/*int main() {

long long x, p, b;
long long sqrtx;
int sign;

while(scanf("%lld", &x)==1 && x!=0) {

sign = (x>0)?1:-1;
if(x<0) x*=-1;

sqrtx = sqrt(x);
for(b=2; b<=sqrtx; b++){

p = log((double)x)/log((double)b)+0.5;
if(x==pow(b, p)) {
if(sign==1) {printf("%lld\n", p); sign =2; break;}
if(sign==-1 && p%2==1) {printf("%lld\n", p); sign=2; break;}
}

}

if(sign!=2)printf("1\n");

}
return 0;
}*/

public static void main(String[] args)
{
long x,p,b;
long sqrtx;
int sign;
Scanner sc = new Scanner(System.in);

while(sc.hasNext() && (x=sc.nextLong()) != 0)
{
sign = (x>0)?1:-1;
if(x<0) x*=-1;

sqrtx = (long)Math.sqrt(x);
for(b=2; b<=sqrtx; b++){

p = (long) (Math.log((double)x)/Math.log((double)b)+0.5);
if(x==Math.pow(b, p)) {
if(sign==1) {System.out.printf("%d%n", p); sign =2; break;}
if(sign==-1 && p%2==1) {System.out.printf("%d%n", p); sign=2; break;}
}

}

if(sign!=2)System.out.printf("1\n");

}



}
}



7.

/**
* Angewandte Mathematik SS 09
10622 Pth Power
* UVa Status: Accepted
* Run Time: 0.150
* Programming Language: C
* Date: 31.03.2009
* @author Doina Logofatu logofatu@hm.edu
*/

/*
x=b^p <=> log x = p log b <=>
p=(log x/log b)

Brute Force - Suche nach dem erst möglichen
Paar (b, p) - b wie klein wie möglich => p maximal

für negatives x darf p nur ungerade sein!

wir vewenden in Formel log((double)x)/log((double)b)+0.5;
die equivalent mit round(log((double)x)/log((double)b))
weil round() in ANSI C nicht vorhanden

Kritische Testcases: 14348907->15, -2147483648->31
*/

#include <stdio.h>
#include <math.h>

int main() {

long long x, p, b;
long long sqrtx;
int sign;

while(scanf("%lld", &x)==1 && x!=0) {

sign = (x>0)?1:-1;
if(x<0) x*=-1;

sqrtx = sqrt(x);
for(b=2; b<=sqrtx; b++){

p = log((double)x)/log((double)b)+0.5;
if(x==pow(b, p)) {
if(sign==1) {printf("%lld\n", p); sign =2; break;}
if(sign==-1 && p%2==1) {printf("%lld\n", p); sign=2; break;}
}

}

if(sign!=2)printf("1\n");

}
return 0;
}

8.

/**
* Angewandte Mathematik SS 09
10622 Perfect Pth Powers
* UVa Status: Accepted
* Run Time: 0.000
* Programming Language: C
* @author Doina Logofatu logofatu@hm.edu

Antwort 2 für 20 und trotzden AC! :-))

*/

/*
dieses Programm gibt für 20 die Antwort 2 zurück und trotzden ACC!
Danke J. Schubert fürs Herausfinden!

*/

#include <stdio.h>
#include <math.h>

long long ggt(long long a, long long b){

if(a<b) return ggt(a, b-a);
if(a>b) return ggt(a-b, b);
return a;
}

long long ppp(long long x){

int p=0, t;
long long j;
int sign = x<0?-1:1;
long long sqrtx;

if(x<0) x=(-1)*x;
sqrtx = (long long)sqrt(x);

while(x%2==0){
p++;
x/=2;
}

for(j=3; x!=1 && p==0 && j<=sqrtx; j+=2){
if(x%j==0){
while(x%j==0){
p++;
x/=j;
}
break;
}
}

if(p==0) return 1;

for(; x!=1 && p!=1 && j<=sqrtx; j+=2){
if(x%j==0){
t=0;
while(x%j==0){
t++;
x/=j;
}
p=ggt(p, t);
}
}

if(sign<0){
while(p%2==0)p/=2;
}

return p;
}

int main() {

long long x;

while(scanf("%lld", &x)==1 && x!=0){

printf("%lld\n", ppp(x));

}

return 0;

}

9.

#include <stdio.h>
#include <math.h>



long long ggt(long long a, long long b){

if(a<b) return ggt(a, b-a);
if(a>b) return ggt(a-b, b);
return a;
}

long long ppp(long long x){

int p=0, t;
long long j;
int sign = x<0?-1:1;
long long sqrtx;

if(x<0) x=(-1)*x;
sqrtx = (long long)sqrt(x);

while(x%2==0){
p++;
x/=2;
}

for(j=3; x!=1 && p==0 && j<=sqrtx; j+=2){
if(x%j==0){
while(x%j==0){
p++;
x/=j;
}
break;
}
}

if(p==0) return 1;

for(; x!=1 && p!=1 && j<=sqrtx; j+=2){
if(x%j==0){
t=0;
while(x%j==0){
t++;
x/=j;
}
p=ggt(p, t);
}
}

/*
- hizugefügt - ACC auch ohne dieses IF - nicht korrekt!
(fall x=20 -> 2)
*/
if(x>1) return 1;
/* */

if(sign<0){
while(p%2==0)p/=2;
}

return p;
}

int main() {

long long x;

while(scanf("%lld", &x)==1 && x!=0){

printf("%lld\n", ppp(x));

}

return 0;

}