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;
}