LightOj 1220 - Mysterious Bacteria (分解质因子x=b^p 中的 x 求最大的 p)

题目链接：http://lightoj.com/volume_showproblem.php?problem=1220

题意：已知 x=b中的 x 求最大的 p，其中 x b p 都为整数

x = (p1*p2*p3*...*pk), pi为素数;则结果就是gcd(a1, a2, a3,...,ak);

当x为负数时，要把ans缩小为奇数;

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <vector>

#include <math.h>

using namespace std;

typedef long long LL;

const int oo = 0xfffffff;

const int N = 1e6+;

const double eps = 1e-;

int f[N], p[N], k = ;

void Init()

{

    for(int i=; i<N; i++)

    {

        if(!f[i]) p[k++] = i;

        for(int j=i; j<N; j+=i)

            f[i] = ;

    }

}

int gcd(int a, int  b)

{

    return b ==  ? a : gcd(b, a%b);

}

int cnt[N];

int main()

{

    Init();

    int T, t = ;

    scanf("%d", &T);

    while(T--)

    {

        LL n;

        int flag = ;

        scanf("%lld", &n);

        if(n < )

        {

            n = -n;

            flag = ;

        }

        int ans = ;

        memset(cnt, , sizeof(cnt));

        for(int i=; i<k && (LL)p[i]*p[i]<=n; i++)

        {

            while(n%p[i] == )

            {

                cnt[i]++;

                n /= p[i];

            }

            if(ans ==  && cnt[i])

                ans = cnt[i];

            else if(cnt[i])

                ans = gcd(cnt[i], ans);

        }

        if(n >  || ans == )

            ans = ;

        if(flag)///负数，结果一定是奇数；

        {

            while(ans% == )

                ans /= ;

        }

        printf("Case %d: %d\n", t++, ans);

    }

    return ;

}

/*

-1000000

1

3

1

*/