LightOJ 1220 Mysterious Bacteria

  • 2018-08-08
  • 8
  • 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.

Sample Input:

3
17
1073741824
25

Sample Output:

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

题目链接

对每个数XX=a^{Y},求Y的最大值。

对于每一个X进行质因数分解

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})}

此时Y​具有最大值。

这道题目X并不是正整数,会有负数,所以当X为负数时需要将其转换为正数求解

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

AC代码:

评论

还没有任何评论,你来说两句吧