LightOJ1220 —— 质因数分解

题目链接:https://vjudge.net/problem/LightOJ-1220

1220 - Mysterious Bacteria
Time Limit: 0.5 second(s) Memory Limit: 32 MB

Dr. Mob has just discovered a Deathly Bacteria. He named it RC-01. RC-01 has a very strange reproduction system. RC-01 lives exactly x days. Now RC-01 produces exactly p new deadly Bacteria where x = bp (where b, p are integers). More generally, x is a perfect pth power. Given the lifetime x of a mother RC-01 you are to determine the maximum number of new RC-01 which can be produced by the mother RC-01.

Input

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with a line containing an integer x. You can assume that x will have magnitude at least 2 and be within the range of a 32 bit signed integer.

Output

For each case, print the case number and the largest integer p such that x is a perfect pth power.

Sample Input

Output for Sample Input

3

17

1073741824

25

Case 1: 1

Case 2: 30

Case 3: 2

题意:

给出一个数x(可以为负数,绝对值大于等于2), 求使得满足 x = b^p 的最大p。 

题解:

1.对x进行质因子分解。

2.取x所有的质因子个数的最大公约数p,如果x为负数,那么p就只能为奇数,所以一直除以2,直到p为奇数。

代码如下:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const int INF = 2e9;
15 const LL LNF = 9e18;
16 const int MOD = 1e9+7;
17 const int MAXN = 1e6+10;
18 
19 bool notprime[MAXN+1];
20 int prime[MAXN+1];
21 void getPrime()
22 {
23     memset(notprime, false, sizeof(notprime));
24     notprime[0] = notprime[1] = true;
25     prime[0] = 0;
26     for (int i = 2; i<=MAXN; i++)
27     {
28         if (!notprime[i])prime[++prime[0]] = i;
29         for (int j = 1; j<=prime[0 ]&& prime[j]<=MAXN/i; j++)
30         {
31             notprime[prime[j]*i] = true;
32             if (i%prime[j] == 0) break;
33         }
34     }
35 }
36 
37 int fatCnt;
38 LL factor[1000][2];
39 void getFactors(LL n)
40 {
41     LL tmp = n;
42     fatCnt = 0;
43     for(int i = 1; prime[i]<=tmp/prime[i]; i++)
44     {
45         if(tmp%prime[i]==0)
46         {
47             factor[++fatCnt][0] = prime[i];
48             factor[fatCnt][1] = 0;
49             while(tmp%prime[i]==0) tmp /= prime[i], factor[fatCnt][1]++;
50         }
51     }
52     if(tmp>1) factor[++fatCnt][0] = tmp, factor[fatCnt][1] = 1;
53 }
54 
55 int gcd(int a, int b)
56 {
57     return b==0?a:gcd(b, a%b);
58 }
59 
60 int main()
61 {
62     getPrime();
63     int T, kase = 0;
64     scanf("%d", &T);
65     while(T--)
66     {
67         LL n;
68         scanf("%lld", &n);
69         getFactors(abs(n));
70         LL p = factor[1][1];
71         for(int i = 2; i<=fatCnt; i++)
72             p = gcd(p, factor[i][1]);
73 
74         while(n<0 &&  p%2==0) p /= 2;
75         printf("Case %d: %d
", ++kase, p);
76     }
77     return 0;
78 }
View Code
原文地址:https://www.cnblogs.com/DOLFAMINGO/p/8377607.html