10622 - Perfect P-th Powers

[pavelph]

And what answers for 1 or (-1) or 0 ???
My prog work on all inputs but WA

[prince56k]

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]

Can anyone tell me why -64 gives result 3 and not 6

M H Rasel

[titid_gede]

-2 ^ 6 = +64 not -64.

regards,
titid

[htl]

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]

[Agusles]

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]

[htl]

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]

for input:

Code: Select all

-2147483648
-2147483647

the output is:

Code: Select all

31
1

[The CodeMaker (AIUB)]

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]

[UFP2161]

Floating point precision.. pow might return something like 2.999999999999999999999999999 for pow(9, 1/2)... you should stick to using integers..

[Morning]

[cpp]
#include <iostream>
using namespace std;
int primes[4800];
int point;
void init()
{
primes[0] = 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[4800],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[0];

for(int j = 1;j < point_a;j++)
{
if (arr[j] < arr[0]) 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]

[sohel]

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]

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[4800];
int point;
void init()
{
//initial the primes array,from 2 to 46340(which is sqrt(2^31))
primes[0] = 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[4800],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[0] = 3
arr[1] = 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[0];
//min store the GCD of numbers in arr[]
for(int j = 1;j < point_a;j++)
{
if (arr[j] < arr[0]) 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]

[dumb dan]

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]

why i can't do that?can u give me a example,thanks