# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------- fast io --------------------
from math import gcd, ceil
def prod(a, mod=10**9+7):
ans = 1
for each in a:
ans = (ans * each) % mod
return ans
def lcm(a, b): return a * b // gcd(a, b)
def binary(x, length=16):
y = bin(x)[2:]
return y if len(y) >= length else "0" * (length - len(y)) + y
from collections import Counter
def gcd(x, y):
"""greatest common divisor of x and y"""
while y:
x, y = y, x % y
return x
def memodict(f):
"""memoization decorator for a function taking a single argument"""
class memodict(dict):
def __missing__(self, key):
ret = self[key] = f(key)
return ret
return memodict().__getitem__
def pollard_rho(n):
"""returns a random factor of n"""
if n & 1 == 0:
return 2
if n % 3 == 0:
return 3
s = ((n - 1) & (1 - n)).bit_length() - 1
d = n >> s
for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
p = pow(a, d, n)
if p == 1 or p == n - 1 or a % n == 0:
continue
for _ in range(s):
prev = p
p = (p * p) % n
if p == 1:
return gcd(prev - 1, n)
if p == n - 1:
break
else:
for i in range(2, n):
x, y = i, (i * i + 1) % n
f = gcd(abs(x - y), n)
while f == 1:
x, y = (x * x + 1) % n, (y * y + 1) % n
y = (y * y + 1) % n
f = gcd(abs(x - y), n)
if f != n:
return f
return n
@memodict
def prime_factors(n):
"""returns a Counter of the prime factorization of n"""
if n <= 1:
return Counter()
f = pollard_rho(n)
return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)
def distinct_factors(n):
"""returns a list of all distinct factors of n"""
factors = [1]
for p, exp in prime_factors(n).items():
factors += [p**i * factor for factor in factors for i in range(1, exp + 1)]
return factors
def all_factors(n):
"""returns a sorted list of all distinct factors of n"""
small, large = [], []
for i in range(1, int(n**0.5) + 1, 2 if n & 1 else 1):
if not n % i:
small.append(i)
large.append(n // i)
if small[-1] == large[-1]:
large.pop()
large.reverse()
small.extend(large)
return small
for _ in range(int(input()) if not True else 1):
#n = int(input())
n, k = map(int, input().split())
#a, b = map(int, input().split())
#c, d = map(int, input().split())
a = list(map(int, input().split()))
count = {}
for i in a:
if i not in count:
count[i] = 0
count[i] += 1
#b = list(map(int, input().split()))
#s = input()
af = all_factors(k)
fuc = set()
for f1 in af:
for f2 in af:
if f1*f2 > k or k % (f1*f2) != 0:continue
f3 = k // (f1 * f2)
x = sorted([f1, f2, f3])
fuc.add((x[0], x[1], x[2]))
ans = 0
for x, y, z in fuc:
try:
if x == y == z:
ans += (count[x]*(count[x]-1)*(count[x]-2))//6
continue
if x == y:
ans += (((count[x]*(count[x]-1))//2) * count[z])
continue
if y == z:
ans += (((count[y]*(count[y]-1))//2) * count[x])
continue
ans += (count[x] * count[y] * count[z])
except:
pass
print(ans)
Comments
0 B
|👍
/👎