OJ Board

Posted: **Thu Sep 04, 2014 12:14 am**

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

Posted: **Fri Dec 04, 2015 10:47 am**

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;
}

Posted: **Wed Mar 15, 2017 3:36 pm**

Your code fails some test cases on Morass's last input. https://www.udebug.com/UVa/10622

OJ Board

10622 - Perfect P-th Powers

Re: 10622 - Perfect Pth Powers

Re: 10622 - Perfect P-th Powers

Re: 10622 - Perfect P-th Powers