查找给定元素的可能功率计数

Question

给你一个包含 N 个整数的数组 A。如果对于任何 Y >0 和 Z>1

，X 可以写为 Y**Z，则 A 中的元素 X 称为完美元素

1<= N <= 10^5
1<= A[i] <= 10^5

输入：

2
9
6

输出

9可以写成3^2

def solve(N,A):
    count=0
    for i in A:
        for j in range(1,int(i)//2):
            for k in range(1,int(j):
                if j**k == int(i):
                    count=count+1
                    i = i + 1
    return count

这种方法可以为我系统中的任何类型的输入提供正确答案，除非它是竞争性编码 IDE 错误消息显示已超出时间限制我该如何克服这个问题？

Answer 1

您可以尝试简单的预处理。首先，根据限制，你需要检查大约 n * 20 个数字（因为 2 ** 20 > N），所以它是 O(n) - 很好，接下来当你处理所有可能的数字时，你可以简单地比较你的输入预处理数据如下：

def solve(n, a):
    MAXN = 10 ** 5 + 1
    is_perfect = [False] * MAXN

    for number in range(1, MAXN):
        for power in range(2, 20):
            if number ** power > MAXN:
                break
            is_perfect[number**power] = True

    counter = 0

    for element in a:
        if is_perfect[element]:
            counter = counter + 1

    return counter

最终复杂度为O(n)

查找给定元素的可能功率计数

Find count of possible power of the given element

python

algorithm

performance