Please help me solve ICPC16D

help
1

HI, I have a problem with “Good Sets Problem Code: ICPC16D”. The question seems to be easy but my code is giving wrong answer it seems. It actually works for example and test cases which I prepared. Can someone help me to find where the problem is. My code is :

def findans(n,arr):    
    global ans
    ans= [0]*750001
    val=0
    arr.sort()
    for i in range(len(arr)-1,-1,-1):
        finddivs(i,arr)
    print((sum(ans))%(10^9+7))
def finddivs(i,arr):
    global ans
    divs=1
    for j in range(i+1,len(arr)):
        if(arr[j]%arr[i]==0):
            divs=(divs+ans[j])%(10^9+7)
    ans[i]=divs
n=int(input().strip())
for i in range(n):
    n1=int(input().strip())
    arr=[int(temp) for temp in input().strip().split(' ')]
    findans(n1,arr)
2

I am currently at phone and couldnt give the Q the perfect formatting. Will be glad if anyone else helped :slight_smile:

3

Change 10^9+7 to 10**9+7, ‘^’ is the symbol for bit-wise XOR, ‘**’ is the symbol for exponentiation in python. I got TLE after changing that in your code, your logic is correct, but its not fast enough. Your ‘finddivs’ method can be improved, you don’t have to go through all the remaining numbers in the array, think about it :slight_smile:

3 Likes