Posted: 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)
(thought I'd be able to edit my post with an example before you read it)
Page 3 of 4
Posted: Sun Oct 03, 2004 6:06 pm
oh,yeah,i forgot this one,thanks,indeed
10622 TLE
Posted: 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)
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;
}
Posted: 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.
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.
Posted: 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!!
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!!
Posted: 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.
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.
Posted: 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!!!!!
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!!!!!
Posted: Sat Mar 12, 2005 1:23 pm
For anyone who may need some sample I/O on this problem.
INPUT
OUTPUT
INPUT
Code: Select all
-1
-16
-27
-81
-243
-244140625
-48828125
-134217728
1
17
25
125
81
107374182
134217728
2147483647
1073741824
-2147483648
0OUTPUT
Code: Select all
1
1
3
1
5
3
11
27
1
1
2
3
4
1
27
1
30
3110622 the question of Time Limit Exceeded
Posted: 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;
}
#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;
}
WA_please help
Posted: 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:
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;
}
}Re:farzane
Posted: Mon Nov 12, 2007 1:04 pm
Farzane wrote:
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.....
I think the problem in your algorithm is inI'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
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.....
Re: 10622 - Perfect Pth Powers
Posted: 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.
(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();
}
Re: 10622 - Perfect Pth Powers
Posted: Sun May 29, 2011 11:24 am
(3) and (4) are not sufficient.
Re: 10622 - Perfect Pth Powers
Posted: Sun Aug 14, 2011 1:50 pm
Nice problem, it seemed easy but a few tricky cases.
Some inputs:
You should get AC if your output matches with the output as above.
Regards
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
0Code: Select all
2
1
2
2
9
2
3
3
1
2
6
3
7
1
2
1
1
4
1
31
Regards
Re: 10622 - Perfect Pth Powers
Posted: 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.