## 10622 - Perfect P-th Powers

Moderator: Board moderators

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg
And what answers for 1 or (-1) or 0 ???
My prog work on all inputs but WA prince56k
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm
to pavel......

there mentioned that the input magnitude will be at least two . so no print will for 1 (-1) ........... i don't think that that data are given in the input file.

Input:
-2048
-64
64
512
-512

output:
11
3
6
9
9[/quote]

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Contact:
Can anyone tell me why -64 gives result 3 and not 6 M H Rasel

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
-2 ^ 6 = +64 not -64.

regards,
titid
Kalo mau kaya, buat apa sekolah?

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
I tried many times and got many WA... I don't know what's wrong with my code. I'm sure that the prime table has no fault. I post part of my code hoping someone would point out the bug in my code.
[c]
Silly code could mislead somebody... so deleted.. [/c]
Last edited by htl on Fri Jul 02, 2004 5:48 am, edited 2 times in total.

Agusles
New poster
Posts: 1
Joined: Sat Oct 11, 2003 12:22 am
I'm having WA with this approach. I search for the repeated factors of the number and check if can be a power (factors exponent have to be equal). Can anyone help me please?

[cpp]#include <stdio.h>
#include <iostream.h>

long long inp,n,i,c; /*change to long lon*/
long act,maxim;

int main()
{
cin>>inp;
while (inp!=0)
{
n=inp<0?-inp:inp;
c=n;
maxim=act=0;
while (n%2==0)
{
n/=2;
maxim++;
}
for (i=3;i*i<=c && maxim!=1;i+=2)
{
while (n%i==0)
{
n/=i;
act++;
}
if (act>0)
{
if (maxim == 0)
maxim=act;
else if (act != maxim)
{
maxim=1;
}
act=0;
}
}
if (inp<0 && maxim!=0 && maxim%2==0)
{
do
{
maxim/=2;
}
while (maxim%2==0);
}
printf("%ld\n",(maxim==0)?1:maxim);
cin>>inp;
}
return 0;
}[cpp][/cpp][/cpp]
Gen2

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
After thinking, I got my final version of my algo.
1.Checking if there is a power of a prime=|n| from the smallest in the prime table.
2.Checking the times. If n>0 then print the times. If n<0 then dividing the times with 2 until times%2==1, then print times.

Is there something wrong in my algorithm?

Alexei Rybalkin
New poster
Posts: 6
Joined: Mon Dec 01, 2003 5:16 pm
Location: Orenburg, Russia
for input:

Code: Select all

``````-2147483648
-2147483647
``````
the output is:

Code: Select all

``````31
1
``````

The CodeMaker (AIUB)
New poster
Posts: 6
Joined: Fri Aug 06, 2004 10:00 am
Contact:
HI, Here is my code.....can anyone tell me why I get WA? [c]#include<stdio.h>
#include<math.h>

void main()
{
double pp,num,snum;
int i;

while(scanf("%lf",&num)==1)
{
if(!num)
break;
snum=num;

if(num<0)
num=-num;
for(i=31;i>=1;i--)
{
pp=pow(num,1.0/i);

if(pp-floor(pp)==0) /*checking the fraction */
{
if(snum>0 || i%2) /* if number is +ve or power is +ve */
{
printf("%d\n",i);
break;
}
}
}
}
}
[/c]
Programming Is An Art....You Have To Feel It...

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Floating point precision.. pow might return something like 2.999999999999999999999999999 for pow(9, 1/2)... you should stick to using integers..

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

### 10622 why WA?

[cpp]
#include <iostream>
using namespace std;
int primes;
int point;
void init()
{
primes = 2;
point = 1;
int flag;
for(int i = 3;i < 46340;i += 2)
{
flag = 1;
for(int j = 0;j < point && primes[j] * primes[j] <= i;j++)
{
if(i % primes[j] == 0)
{
flag = 0;
break;
}
}
if(flag) {primes[point++] = i;}
}
}
int count(long long n)
{
int arr,min;
int point_a = 0;
for(long long i = 0;i < 4792 && primes <= n;i++)
{
if(n % primes == 0)
{
arr[point_a] = 0;
while(n % primes == 0)
{
arr[point_a]++;
n /= primes;
}
point_a++;
}
}
if(n != 1)
{
return 1;
}
min = arr;

for(int j = 1;j < point_a;j++)
{
if (arr[j] < arr) min = arr[j];
if(arr[j] != arr[j - 1])
{
if(arr[j] % arr[j - 1] && arr[j - 1] % arr[j])
{
return 1;
}
}
}
return min;
}
int main()
{
init();
long long n;
while(cin >> n)
{
if(n == 0) break;
if(n < 0) n *= -1;
cout << count(n) << endl;
}
return 0;
}
[/cpp]
"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

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Instead of just posting your code, why don't you describe the algorithm you have used.

I'm sure, in this way you will get more replies. Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China
i really want to do that,but because of my poor english,i don't know whether i can explain it well [cpp]
#include <iostream>
using namespace std;
int primes;
int point;
void init()
{
//initial the primes array,from 2 to 46340(which is sqrt(2^31))
primes = 2;
point = 1;
int flag;
for(int i = 3;i < 46340;i += 2)
{
flag = 1;
for(int j = 0;j < point && primes[j] * primes[j] <= i;j++)
{
if(i % primes[j] == 0)
{
flag = 0;
break;
}
}
if(flag) {primes[point++] = i;}
}
}
int count(long long n)
{
int arr,min;
int point_a = 0;
/**********************************************
here i divide n by every primes in the primes[]
if n % primes[] == 0 until the number in primes[]
is larger than n,put the times in arr[].
for example
392 = 2 * 2 * 2 * 7 * 7
than the arr[] will be
arr = 3
arr = 2
***********************************************/
for(long long i = 0;i < 4792 && primes <= n;i++)
{
if(n % primes == 0)
{
arr[point_a] = 0;
while(n % primes == 0)
{
arr[point_a]++;
n /= primes;
}
point_a++;
}
}
//if n still != 0,n must be larger than 46340,then return 1
if(n != 1)
{
return 1;
}
min = arr;
//min store the GCD of numbers in arr[]
for(int j = 1;j < point_a;j++)
{
if (arr[j] < arr) min = arr[j];
if(arr[j] != arr[j - 1])
{
if(arr[j] % arr[j - 1] && arr[j - 1] % arr[j])
// the GCD of arr[j] and arr[j + 1] is 1
{
return 1;
}
}
}
return min;
}
int main()
{
init();
long long n;
while(cin >> n)
{
if(n == 0) break;
if(n < 0) n *= -1;
cout << count(n) << endl;
}
return 0;
}
[/cpp]
"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

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
You can't just multiply negative values by -1 and expect to get the right answer. For example:

input:

Code: Select all

``````4
-4
0``````
ouput:

Code: Select all

``````2
1``````

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China
why i can't do that?can u give me a example,thanks
"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