10622 - Perfect P-th Powers

[dumb dan]

ah sorry... example is above...
(thought I'd be able to edit my post with an example before you read it)

[Morning]

oh,yeah,i forgot this one,thanks,indeed

[midra]

Hi ..I don't know why it gives me TLE
I don't know how to increase the speed
the code make this
read the number and calculate the primes that divide the number
for every prime that divides the number it saves how many times it divides it, and then it calculate the gcd between the exponents of the primes and this is the maximum power
for example:
n=19208=2^3*7^4;
my prog save first the 3 and then the 4. It makes gcd(4,3) and it is 1 so maximum power is 1
n=5184=2^6*3^4
my program calculates gcd(6,4)==2 so maximum power is 2

welll...for better understanding here is my code (and sorry for my bad english)

#include <stdio.h>
int min;

gcd(int a, int b){
if(b>a) gcd(b,a);
if(b==0) {
min=a;
return 1;
}
gcd(b,a%b);
}

calc(int n,int neg){
int i=3,j=0;
min=1;
if(n%2==0){
while(n%2==0){
n/=2;
j++;
}
min=j;
if(j==1){
printf("1\n");
return 1;
}
}
j=0;
while(i*i<=n){
if(n%i==0){
while(n%i==0){
n/=i;
j++;
}
if(j==1){
printf("1\n");
return 1;
}
if(min==1) min=j;
else gcd(min,j);
if(min==1){
printf("1\n");
return 1;
}
}
j=0;
i+=2;
}
if(neg==1){
if(min%2==0)
while(min%2==0) min/=2;
printf("%d\n",min);
}
else
printf("%d\n",min);
}

int main()
{
int n;
while(scanf("%d",&n)&n!=0){
if(n==-2147483647 || n==2147483647) printf("1\n");
if(n<0) calc(-n,1);
else calc(n,0);
}
return 0;
}

[Adrian Kuegel]

I think you are getting overflow with the comparison i*i<=n.
Another thing: you should know that the range of 4-byte integer is -2147483648 to 2147483647, so I guess your program also doesn't work for -2147483648.
The easiest way would be to make all variables long long. This should at least avoid the TLE. And if you want to make your program still faster, store all primes up to sqrt(2^31) in an array.

[midra]

thnaks for your reply
I change for long long like you say but I get TLE again
I will try by saving the primes after sqrt(2^31)
anda by the way
why do you think that the program gets overflow with the comparisson i*i<=n ????

thanks again!!

[Adrian Kuegel]

maybe I am wrong, but try the input 2147483645
Because i goes up in steps of 2, i=46339 is the biggest allowed value, but 46341*46341 > 2147483647 and will overflow and become a negative number, therefore your loop will continue.

[midra]

thank you so much Adrian!
I try changing ALL variables to long long and still got tle, later I will try by saving the primes...
"46341*46341 > 2147483647 "
I have never think in this.... you know a lot, welll..you was in the 1st place in the rank for a lot of time, by the way Why don't you get the first place again?have no time?

thanks again and good luck!!!!!

[Sedefcho]

For anyone who may need some sample I/O on this problem.

INPUT

Code: Select all

-1
-16
-27
-81
-243
-244140625
-48828125
-134217728
1
17
25
125
81
107374182
134217728
2147483647
1073741824
-2147483648
0

OUTPUT

Code: Select all

1
1
3
1
5
3
11
27
1
1
2
3
4
1
27
1
30
31

[athlon19831]

#include "iostream.h"
#include "stdio.h"
int main(int argc, char* argv[])
{
int x;
int i,j;
int s;
int j1;
j1=1;
int i1;
while(cin>>x)
{
if(x==0)
break;
else if(x>0)
{

for(i=1;i<=x;i++)
{
s=1;
for(j=1;j<=x;j++)
{
s=s*i;
if(s>x)
break;
//cout<<"s="<<s<<endl;
if(s==x)
{
j1=j;
j=x+1;
i=x+1;
}
}
}

}
else if(x<0)
{
x=-x;
for(i=1;i<=x;i++)
{
s=-i;
i1=1;
//cout<<"s=-i:"<<s<<endl;
for(j=1;j<=x;j++)
{
if(j==1)
i1=s;
else
{
i1=i1*s;
}
if(i1<-x)
break;
//cout<<"i1="<<i1<<endl;
if(i1==(-x))
{
j1=j;
j=x+1;
i=x+1;
}
}
}
}
cout<<j1<<endl;
j1=1;
}
return 0;
}

[farzane]

I'm getting WA and don't undrestand where is my mistake.could someone please help me?
my algorithm:
1)producing prime numbers up to the sqrt of MAX_int(our limit)
2)when reading an input produce all powers of its primefactors and store them
3)getting gcd between powers
4)(if n<0 and gcd%2==0 )gcd/=2
5)for case n=-2147483648 I just print 31 and go to read next input
and here is my code:

Code: Select all

#include<iostream.h>
#include<math.h>
const int maxprime=70000;
bool isprime[maxprime];
int prime[maxprime],primesize;

int gcd2n(int a,int b){
	int c;
	if(a<b){
		c=a;
		a=b;
		b=c;
	}
	c=a%b;
	while(c>0){
		a=b;
		b=c;
		c=a%b;
	}
	return b;
}

int gcd(int A[],int n){
	int I,ans;
	if(n==1)return A[0];
	ans=gcd2n(A[n-2],A[n-1]);
	for(I=0;I<n-2;I++)
		ans=gcd2n(A[I],ans);
	return ans;
}

void main(){
	int ans,I,J,n,s,m,factno,factpow[40],flag;
	for(I=0;I<maxprime;I++)
		isprime[I]=true;
	isprime[0]=isprime[1]=false;
	for(I=2;I<maxprime;I++)
		if(isprime[I]){
			prime[primesize++]=I;
			for(J=I+I;J<maxprime;J+=I)
				isprime[J]=false;
		}

		cin>>n;
		while(n!=0){
			if(n==-2147483648){
				cout<<31<<endl;
				cin>>n;
				continue;
			}
			if(n<0){
				n=n*-1;
			    flag=-1;
			}else flag=1;
			s=sqrt(n);
			m=n;
			factno=0;
			if(n<maxprime&&isprime[n]){
				factpow[0]=1;
				factno=1;
			}else{
				for(I=0;I<primesize&&prime[I]<=s&&m>1;I++)
					if(m%prime[I]==0){
						factpow[factno]=0;
						while(m%prime[I]==0){
							m/=prime[I];
							factpow[factno]++;
						}

						if(flag==-1&&(factpow[factno]%2==0))factpow[factno]/=2;
						factno++;
						if(m<maxprime&&isprime[m]){
			            	factpow[factno]=1;
				            factno++;
							m=1;
						}  

					}
				if(m>1)
					factpow[factno++]=1;
			}

			ans=gcd(factpow,factno);
			cout<<ans<<endl;
			cin>>n;
		}
}

[Bishnu]

Farzane wrote:

I'm getting WA and don't undrestand where is my mistake.could someone please help me?
my algorithm:
1)producing prime numbers up to the sqrt of MAX_int(our limit)
2)when reading an input produce all powers of its primefactors and store them
3)getting gcd between powers
4)(if n<0 and gcd%2==0 )gcd/=2
5)for case n=-2147483648 I just print 31 and go to read next input

I think the problem in your algorithm is in
4)(if n<0 and gcd%2==0)gcd/=2

For this your code give wrong output for -65536
For -65536 the correct output is 1

I think you have to change 4) by
(if n<0 and gcd%2==0)
{
while(gcd%2==0)gcd/=2;
}

Good luck.....

[stcheung]

I got over 10 WA and passed every single test case posted here. My algorithm is same as that mentioned in a previous post:
(1) Get all primes < sqrt(MAX)
(2) For each prime that divides the input, store the power in a hashmap
(3) Iterate over the value of the hashmap to see if they all equal 1 value
(4) If so, and if input is positive return that value
(5) If so, but input is negative then keep dividing that value by 2 until that value is odd
(6) I also handled the maximum negative input case

Any idea? Below is my code. Thanks a lot.

Code: Select all

static int[] findPrimes(int n) {
	int primes[] = new int[100000];
	int numPrime = 0;
	int MAX = n+1;
	boolean notPrime[] = new boolean[MAX];
	for(int i=2; i<MAX; i+=2) {
		if(notPrime[i]) continue;
		primes[numPrime++] = i;
		for(int j=i; j<MAX; j+=i) {
			notPrime[j] = true;
		}
		if(i==2)
			i--;
	}
	int results[] = new int[numPrime];
	System.arraycopy(primes, 0, results, 0, numPrime);
	return results;
}

public static void main(String args[]) throws Exception {
	int primes[] = findPrimes((int)Math.sqrt(Integer.MAX_VALUE));
	
	while(true) {
		String line = readLine();
		if(line.equals("")) continue;
		int N = toInt(line);
		if(N == 0) break;
		
		if(N == Integer.MIN_VALUE) {
			println(31);
			continue;
		}
		
		int origN = N;
		N = (N < 0 ? -N : N);
		
		HashMap<Integer, Integer> powers = new HashMap<Integer, Integer>();
		for(int p : primes) {
			if(N == 1)
				break;
			if(N%p != 0) 
				continue;
			
			powers.put(p, 0);
			while(N%p == 0) {
				powers.put(p, 1 + powers.get(p));
				N/=p;
			}
		}
		if(N > 1)
			powers.put(N, 1);
		
		int power = -1;
		for(int p : powers.values()) {
			if(power == -1)
				power = p;
			if(power != p) {
				power = -1;
				break;
			}
		}
		if(power == -1 || power == 1) {
			println(1);
			continue;
		}
		if(origN < 0) {
			while(power%2 == 0) {
				power/=2;
			}
		}
		println(power);
	}
	flush();
}

[zobayer]

(3) and (4) are not sufficient.

[plamplam]

Nice problem, it seemed easy but a few tricky cases.
Some inputs:

Code: Select all

2025
-2025
4624
4900
512
176400
1540798875
-1540798875
648000
746496
2985984
-2985984
-612220032
204073344
3779136
-75325538
75325538
418161601
-418161601
-2147483648
0

Code: Select all

2
1
2
2
9
2
3
3
1
2
6
3
7
1
2
1
1
4
1
31

You should get AC if your output matches with the output as above.
Regards

[Shafaet_du]

No need of factorization,gcd etc,this problem can be solved by brute force with some little clever pruning.