10622 - Perfect P-th Powers

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Sun Oct 03, 2004 5:45 pm

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

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Post by Morning » Sun Oct 03, 2004 6:06 pm

oh,yeah,i forgot this one,thanks,indeed
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

10622 TLE

Post by midra » Fri Jan 21, 2005 5:02 am

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Jan 21, 2005 7:16 pm

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
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

Post by midra » Mon Jan 24, 2005 1:05 am

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Jan 24, 2005 2:12 am

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
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

Post by midra » Fri Jan 28, 2005 4:19 am

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!!!!! :D

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Sat Mar 12, 2005 1:23 pm

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
New poster
Posts: 20
Joined: Thu Jan 19, 2006 2:32 pm

10622 the question of Time Limit Exceeded

Post by athlon19831 » Sun Jan 22, 2006 6:11 pm

#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
New poster
Posts: 26
Joined: Thu Jun 15, 2006 9:26 am

WA_please help

Post by farzane » Thu Oct 19, 2006 8:08 pm

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
New poster
Posts: 1
Joined: Mon Nov 12, 2007 12:26 pm
Contact:

Re:farzane

Post by Bishnu » Mon Nov 12, 2007 1:04 pm

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.....
Getting Boared with WA,TLE,PE,RE!!!!!!!!!

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 10622 - Perfect Pth Powers

Post by stcheung » Sat Mar 14, 2009 10:32 am

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
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 10622 - Perfect Pth Powers

Post by zobayer » Sun May 29, 2011 11:24 am

(3) and (4) are not sufficient.
You should not always say what you know, but you should always know what you say.

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 10622 - Perfect Pth Powers

Post by plamplam » Sun Aug 14, 2011 1:50 pm

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 :wink:
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10622 - Perfect Pth Powers

Post by Shafaet_du » Tue Sep 20, 2011 6:50 pm

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

Post Reply

Return to “Volume 106 (10600-10699)”