Submission #8012866

---

Source Code Expand

#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
from fractions import gcd

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K = getlist()
	A = getlist()
	G = []
	if ((K ** 0.5) // 1) ** 2 == K:
		x = int((K ** 0.5) // 1)
		for i in range(1, x):
			if K % i == 0:
				G.append(i)
		n = len(G)
		for i in range(n):
			G.append(K // G[i])
		G.append(int((K ** 0.5) // 1))

	else:
		x = int((K ** 0.5) // 1)
		for i in range(1, x + 1):
			if K % i == 0:
				G.append(i)
		n = len(G)
		for i in range(n):
			G.append(K // G[i])

	D = defaultdict(int)
	for i in range(N):
		D[gcd(A[i], K)] += 1
	
	ans = 0
	n = len(G)
	for i in range(n):
		for j in range(i, n):
			if (G[i] * G[j]) % K == 0:
				if i != j:
					ans += (D[G[i]] * D[G[j]])
				else:
					ans += ((D[G[i]] - 1) * D[G[j]]) // 2
	print(ans)

	


if __name__ == '__main__':
	main()

Submission Info

Judge Result