Submission #6899253

---

Source Code Expand

n,k=map(int,input().split())
a=list(map(int,input().split()))

def soinsuu(a):
    soinsuu_dict=dict()
    j=2
    while(a>1):
        for i in range(j,int(a**0.5)+1):
            if a%i==0:
                if i in soinsuu_dict.keys():
                    soinsuu_dict[i]+=1
                else:
                    soinsuu_dict[i]=1
                a,j=a//i,i
                break
        else:
            if a in soinsuu_dict.keys():
                soinsuu_dict[a]+=1
            else:
                soinsuu_dict[a]=1
            a=1
            break
    return soinsuu_dict

def yakusuu(a):
    yakusuu=set()
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            yakusuu.add(i)
            yakusuu.add(a//i)
    yakusuu=sorted(list(yakusuu),reverse=True)
    return yakusuu

soinsuu_dict=soinsuu(k)
y_k=yakusuu(k)
d={y:0 for y in y_k}
for i in a:
    temp=1
    for j in soinsuu_dict.keys():
        for _ in range(soinsuu_dict[j]):
            if i%j==0:
                i=i//j
                temp*=j
            else:
                break
    d[temp]+=1
    
ans=0
for y in y_k:
    for z in y_k:
        if y<z:
            if (y*z)%k==0:
                ans+=d[y]*d[z]
        elif y==z:
            if (y*z)%k==0:
                ans+=d[y]*(d[y]-1)//2
print(ans)

Submission Info

Judge Result