## 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

matrix2220
New poster
Posts: 9
Joined: Mon Jul 07, 2014 3:37 pm
Contact:

### Re: 10622 - Perfect Pth Powers

Hi There, This is an explanation for the solution of the problem

Theorem:
All the powers in the prime factorization of an integer n is even iif n is a perfect square power number.

This Theorem can be extended to any perfect pth power, so we will say:
"All the powers in the prime factorization of an integer n is divisible by p iif n is a perfect p-th power number."

So what we need to do now is to get prime factorization for n and save all it's powers.
If n is -ve then multiply it by -1 to make it +ve, we will handle -ve later.
Then try all valid powers from 32 down to 1
if all powers are divisible by current tested valid power then we found a candidate solution but we need to check for one thing.
if the given number is +ve then we don't need to check for any thing, congratulations we found a solution.
if the given number is -ve then we should make sure that the valid power we found is odd in order to preserve the -ve value if so then we found a solution.
The reason for that is ex. 64 = 2^6 But -64 = -(2^2)^3 = -4^3

Hope That Helps.

------------------------------
Special Thanks: http://pavelsimo.blogspot.com/2012/06/u ... owers.html
Abdelrahman Ali (MaTrix)

Tanmoy1228
New poster
Posts: 10
Joined: Sat Jul 19, 2014 2:55 am

### Re: 10622 - Perfect P-th Powers

Verdict: WA
but can not find the problem
please help someone.......

Code: Select all

``````#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
ll n,m,i,j,ans,a,c;
double b;
while(scanf("%lld",&n) && n)
{
ans=1;
m=n;
n=abs(n);
for(i=2; i<33; i++)
{
b=1.0/(i*1.0);
a=ceil( pow( n,b ) );
c=ceil( pow( a,i ) );
//cout<<a<<" "<<c<<endl;

if(c==n)
ans=i;
}
if(m<0 && ans%2==0)
{
n=ans;
m=n;
ans=0;
for(i=2; i*i<=m; i++)
{
if(n%i==0)
{
while(n%i==0)
n=n/i;
ans=max(ans,i);
}
}
ans=max(ans,n);
if(ans==2)
ans=1;
}
printf("%lld\n",ans);
}

return 0;
}

``````

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10622 - Perfect P-th Powers

Your code fails some test cases on Morass's last input. https://www.udebug.com/UVa/10622
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman