python - 厨师和最高星级(CodeChef十月的长期挑战)

Question

https://www.codechef.com/OCT19B/problems/MSV

约束：

1≤T≤10
1≤N≤105
每个有效i1≤Ai≤106
所有测试用例的N之和不超过100,000。

我的代码中获得了TLE：不知道为什么？

import math

t=int(input())
for _ in range(t):
    n=int(input())
    a=[int(x) for x in input().split()]
    dic={}
    ans=0

    for i in a:
        j=1
        while(j<= math.sqrt(i)):
            if(i%j==0):
                dic[j]=0
                if(j!=i//j):
                    dic[i//j]=0
            j=j+1

    for i in a:
        count=0
        if(dic[i]!=0):
            count=dic[i]
        j=1
        while(j<= math.sqrt(i)):
            if(i%j==0):
                dic[j]+=1
                if(j!=i//j):
                    dic[i//j]+=1
            j=j+1
        ans=ans if ans>count else count
    print(ans)

Answer 1

我尝试使用cpp实现它，但它仍然提供TLE，您解决了吗？