Uva 10622 - Perfect P-th Powers

/*

    Verdict: Accepted
    1st Approach


*/

#include<bits/stdc++.h>

#define limit 1000005
#define psb push_back
#define sf scanf
#define pf printf

using namespace std;

template<class T> T gcd(T a, T b) {return b!=0 ? gcd<T>(b,a%b) : a;}

typedef long long LL;
typedef unsigned long long ull;
typedef vector<LL>vll;

int prime[(limit >> 6) + 1];
LL prm[(limit>>1) + 9], plen=0;

#define setbit(n) (prime[n>>6] |= (1 << ((n>>1) & 31)))
#define checkbit(n) (prime[n>>6] & (1 << ((n>>1) & 31)))

void sieve()
{
    LL i,j;

    for(i=3; i*i<=limit; i+=2)
    {
        if(!checkbit(i))
        {
            for(j=i*i;j<=limit;j+=i+i)
            {
                setbit(j);
            }
        }
    }

    prm[plen++] = 2;

    for(i=3; i<=limit; i+=2)
    {
        if(!checkbit(i))
        {
            prm[plen++] = i;
        }
    }
}

int factorize(LL n)
{
    int count_factor=0, mini=100005;

    for(int i=0;i<plen and prm[i] * prm[i] <= n; i++)
    {
        if(!(n%prm[i]))
        {
            count_factor=0;

            while(!(n%prm[i]))
            {
                count_factor++;
                n/=prm[i];
                if(n==0 or n==1)break;
            }

            mini = min(mini, count_factor);
        }
    }

    if(n > 1)
    {
        mini = 1;
    }

    return mini;
}

int main()
{
    sieve();
    LL num;
    while(~sf("%lld",&num) and num)
    {
        bool fl=false;

        if(num < 0)
        {
            fl=true;
            num*=-1;
        }

        int res = factorize(num);

        if(fl)
        {
            while(!(res&1))
            {
                res/=2;
            }
        }

        pf("%d\n",res);
    }

    return 0;
}
===================================================================





/*

    Verdict: Accepted
    2nd Approach

*/



#include<bits/stdc++.h>

#define limit 1000005
#define psb push_back
#define sf scanf
#define pf printf

using namespace std;

template<class T> T gcd(T a, T b) {return b!=0 ? gcd<T>(b,a%b) : a;}

typedef long long LL;
typedef unsigned long long ull;
typedef vector<LL>vll;

int prime[(limit >> 6) + 1];

#define setbit(n) (prime[n>>6] |= (1 << ((n>>1) & 31)))
#define checkbit(n) (prime[n>>6] & (1 << ((n>>1) & 31)))

vll v;

void sieve()
{
    LL i,j;

    for(i=3; i*i<=limit; i+=2)
    {
        if(!checkbit(i))
        {
            for(j=i*i;j<=limit; j+=i+i)
            {
                setbit(j);
            }
        }
    }

    v.psb(2);

    for(i=3; i<=limit; i+=2)
    {
        if(!checkbit(i))
        {
            v.psb(i);
        }
    }

    //cout << v.size();
    //for(i=0;i<v.size();i++)cout<<v[i] << " ";
}

int factorize(LL n)
{
    LL i,len=v.size(); //cout << len;
    int now=0, ans=1;
    bool f=false;

    for(i=0;i<len and v[i]*v[i] <= n; i++)
    {
        now=0;

        if(!(n%v[i]))
        {
            now=0;

            while(!(n%v[i]))
            {
                now++;
                n/=v[i];
                if(n==0 or n==1)break;
            }

            if(!f)
            {
                ans = now;
                f=true;
            }

            ans = gcd<LL>(now, ans); //cout << ans << " ; ";
        }
    }

    if(n > 1)
    {
        ans = 1;
        //ans = gcd<LL>(1,pre);
    }

    //pf("%d\n",ans);
    return ans;
}

int main()
{
    sieve();

    LL num;

    //freopen("input.txt", "r", stdin);

    while(~sf("%lld",&num) and num)
    {
        bool fl=false;

        if(num < 0)
        {
            fl=true;
            num*=-1;
        }

        int res = factorize(num);

        if(fl)
        {
            while(!(res&1))
            {
                res/=2;
            }

            pf("%d\n",res);
        }

        else
        {
            pf("%d\n",res);
        }
    }

    return 0;
}