Problem Solving►UVa

UVa 10622 - Perfect P-th Powers

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

中文網址

Solution

質因數分解後，求各項指數的最大公因數，即是最大的 p 。而負數時要一直除以 2 直到 p 為奇數。

Code

UVa 10622
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<climits>
#define N 46341//sqrt(INT_MAX)

bool sieve[N];
int prime[5000];
int getPrime()
{
    int count = 0;
    for (int i = 2; i < N; i++)
    {
        if (!sieve[i])
        {
            prime[count++] = i;
            for (int j = i + i; j < N; j += i)
                sieve[j] = true;
        }
    }

    return count;
}
inline int gcd(int a, int b)
{
    while (b)
    {
        int temp = a%b;
        a = b;
        b = temp;
    }

    return a;
}
int main()
{
    int m = getPrime();
    int n;
    while (scanf("%d", &n) && n)
    {
        int ans = 0, temp = n;
        
        if (n == INT_MIN)//-2147483648
        {
            puts("31");
            continue;
        }
        else if (n < 0)
            n *= -1;

        //因數分解
        for (int i = 0; i < m&&n >= prime[i] * prime[i]; i++)
        {
            int count = 0;
            while (!(n%prime[i]))
            {
                count++;
                n /= prime[i];
            }

            if (count)
                if (!ans)
                    ans = count;
                else
                    ans = gcd(ans, count);
        }

        if (n != 1)//還有剩下就是質數，其指數為 1
            ans = 1;

        if (temp < 0)//負數處理
            while (!(ans & 1))
                ans /= 2;

        printf("%d\n", ans);
    }

    return 0;
}