Submission #3586421

---

Source Code Expand

from fractions import gcd
from collections import defaultdict
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
dd=defaultdict(int)
for a in A:
    dd[gcd(a,K)]+=1
ans=0
for k,v in dd.items():
    for s,t in dd.items():
        if (k*s)%K==0:
            ans+=v*t
for a in A:
    if a*a%K==0:
        ans-=1
print(ans//2)

Submission Info

Judge Result