LightOJ 1220 Mysterious Bacteria

• 2018-08-08
• 29
• 0

题目:

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.

3
17
1073741824
25

Sample Output:

Case 1: 1
Case 2: 30
Case 3: 2

题目链接

X=p_{1}^{e_{1}}\times p_{2}^{e_{2}}\times…\times p_{k}^{e_{k}}

\thereforeY=gcd(e_{1},e_{2},…,e_{k})时可以将p合并为一个数M

X=M^{gcd(e_{1},e_{2},…,e_{k})}

X为负数且Y最大值为偶数(显然不能为偶数)时，需要将M逐次乘方直到Y为奇数。