Submission #6748721

---

Source Code Expand

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict


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

n, k = li()
a = list(li())

dic = defaultdict(int)
for ai in a:
    dic[gcd(ai, k)] += 1

ans = 0
for k1, v1 in dic.items():
    for k2, v2 in dic.items():
        if k1*k2 % k == 0:
            if k1 == k2:
                ans += v1*(v2-1)
            else:
                ans += v1*v2

print(ans // 2)

Submission Info

Judge Result