Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # ------------------- 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)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement