with some optimization:
\nclass Solution:\n    def countPairs(self, a: List[int], k: int) -> int:\n        z=(l:=len(a))-len(b:=[v for v in a if v%k])\n        o=z*l-z*(z+1)//2\n      
```\nclass Solution:\n    def countPairs(self, a: List[int], k: int) -> int:\n        z=(l:=len(a))-len(b:=[v for v in a if v%k])\n        o=z*l-z*(z+1)//2\n        d=sorted(Counter(w for v in b if ~-(w:=gcd(v,k))).items(),reverse=1)\n        for e,(x,v) in enumerate(d):\n            if x*x%k==0:o+=v*(v-1)//2\n            c,m=0,k//x\n            for y,w in d[:e]:\n                if x*y%k==0:c+=w\n                if y<=m:break\n            o+=v*c\n        return o\n        \n```
['Python3']