Submission #6784065

---

Source Code Expand

def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

n,k=map(int,input().split())
arr=list(map(int,input().split()))
gcds={}
for val in arr:
  tmp=gcd(val,k)
  if tmp not in gcds:
    gcds[tmp]=1
  else:
    gcds[tmp]+=1
ans=0
garr=list(gcds.keys())
for val1 in garr:
  for val2 in garr:
    if (val1*val2)%k!=0:
      continue
    if val1==val2:
      if val1 in gcds:
        ans+=gcds[val1]*(gcds[val2]-1)
    else:
      if val1 in gcds and val2 in gcds:
        ans+=gcds[val1]*gcds[val2]        
print(ans//2)

Submission Info

Judge Result