Advertisement
manish

Untitled

Feb 19th, 2021
690
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 5.42 KB | None | 0 0
  1. # ------------------- fast io --------------------
  2. import os
  3. import sys
  4. from io import BytesIO, IOBase
  5.  
  6. BUFSIZE = 8192
  7.  
  8.  
  9. class FastIO(IOBase):
  10.     newlines = 0
  11.  
  12.     def __init__(self, file):
  13.         self._fd = file.fileno()
  14.         self.buffer = BytesIO()
  15.         self.writable = "x" in file.mode or "r" not in file.mode
  16.         self.write = self.buffer.write if self.writable else None
  17.  
  18.     def read(self):
  19.         while True:
  20.             b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
  21.             if not b:
  22.                 break
  23.             ptr = self.buffer.tell()
  24.             self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
  25.         self.newlines = 0
  26.         return self.buffer.read()
  27.  
  28.     def readline(self):
  29.         while self.newlines == 0:
  30.             b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
  31.             self.newlines = b.count(b"\n") + (not b)
  32.             ptr = self.buffer.tell()
  33.             self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
  34.         self.newlines -= 1
  35.         return self.buffer.readline()
  36.  
  37.     def flush(self):
  38.         if self.writable:
  39.             os.write(self._fd, self.buffer.getvalue())
  40.             self.buffer.truncate(0), self.buffer.seek(0)
  41.  
  42.  
  43. class IOWrapper(IOBase):
  44.     def __init__(self, file):
  45.         self.buffer = FastIO(file)
  46.         self.flush = self.buffer.flush
  47.         self.writable = self.buffer.writable
  48.         self.write = lambda s: self.buffer.write(s.encode("ascii"))
  49.         self.read = lambda: self.buffer.read().decode("ascii")
  50.         self.readline = lambda: self.buffer.readline().decode("ascii")
  51.  
  52.  
  53. sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
  54. input = lambda: sys.stdin.readline().rstrip("\r\n")
  55.  
  56. # ------------------- fast io --------------------
  57. from math import gcd, ceil
  58.  
  59. def prod(a, mod=10**9+7):
  60.     ans = 1
  61.     for each in a:
  62.         ans = (ans * each) % mod
  63.     return ans
  64.  
  65. def lcm(a, b): return a * b // gcd(a, b)
  66.  
  67. def binary(x, length=16):
  68.     y = bin(x)[2:]
  69.     return y if len(y) >= length else "0" * (length - len(y)) + y
  70.  
  71. from collections import Counter
  72.  
  73.  
  74. def gcd(x, y):
  75.     """greatest common divisor of x and y"""
  76.     while y:
  77.         x, y = y, x % y
  78.     return x
  79.  
  80.  
  81. def memodict(f):
  82.     """memoization decorator for a function taking a single argument"""
  83.     class memodict(dict):
  84.         def __missing__(self, key):
  85.             ret = self[key] = f(key)
  86.             return ret
  87.  
  88.     return memodict().__getitem__
  89.  
  90.  
  91. def pollard_rho(n):
  92.     """returns a random factor of n"""
  93.     if n & 1 == 0:
  94.         return 2
  95.     if n % 3 == 0:
  96.         return 3
  97.  
  98.     s = ((n - 1) & (1 - n)).bit_length() - 1
  99.     d = n >> s
  100.     for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
  101.         p = pow(a, d, n)
  102.         if p == 1 or p == n - 1 or a % n == 0:
  103.             continue
  104.         for _ in range(s):
  105.             prev = p
  106.             p = (p * p) % n
  107.             if p == 1:
  108.                 return gcd(prev - 1, n)
  109.             if p == n - 1:
  110.                 break
  111.         else:
  112.             for i in range(2, n):
  113.                 x, y = i, (i * i + 1) % n
  114.                 f = gcd(abs(x - y), n)
  115.                 while f == 1:
  116.                     x, y = (x * x + 1) % n, (y * y + 1) % n
  117.                     y = (y * y + 1) % n
  118.                     f = gcd(abs(x - y), n)
  119.                 if f != n:
  120.                     return f
  121.     return n
  122.  
  123.  
  124. @memodict
  125. def prime_factors(n):
  126.     """returns a Counter of the prime factorization of n"""
  127.     if n <= 1:
  128.         return Counter()
  129.     f = pollard_rho(n)
  130.     return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)
  131.  
  132.  
  133. def distinct_factors(n):
  134.     """returns a list of all distinct factors of n"""
  135.     factors = [1]
  136.     for p, exp in prime_factors(n).items():
  137.         factors += [p**i * factor for factor in factors for i in range(1, exp + 1)]
  138.     return factors
  139.  
  140.  
  141. def all_factors(n):
  142.     """returns a sorted list of all distinct factors of n"""
  143.     small, large = [], []
  144.     for i in range(1, int(n**0.5) + 1, 2 if n & 1 else 1):
  145.         if not n % i:
  146.             small.append(i)
  147.             large.append(n // i)
  148.     if small[-1] == large[-1]:
  149.         large.pop()
  150.     large.reverse()
  151.     small.extend(large)
  152.     return small
  153.  
  154. for _ in range(int(input()) if not True else 1):
  155.     #n = int(input())
  156.     n, k = map(int, input().split())
  157.     #a, b = map(int, input().split())
  158.     #c, d = map(int, input().split())
  159.     a = list(map(int, input().split()))
  160.     count = {}
  161.     for i in a:
  162.         if i not in count:
  163.             count[i] = 0
  164.         count[i] += 1
  165.     #b = list(map(int, input().split()))
  166.     #s = input()
  167.     af = all_factors(k)
  168.     fuc = set()
  169.     for f1 in af:
  170.         for f2 in af:
  171.             if f1*f2 > k or k % (f1*f2) != 0:continue
  172.             f3 = k // (f1 * f2)
  173.             x = sorted([f1, f2, f3])
  174.             fuc.add((x[0], x[1], x[2]))
  175.     ans = 0
  176.     for x, y, z in fuc:
  177.         try:
  178.             if x == y == z:
  179.                 ans += (count[x]*(count[x]-1)*(count[x]-2))//6
  180.                 continue
  181.             if x == y:
  182.                 ans += (((count[x]*(count[x]-1))//2) * count[z])
  183.                 continue
  184.             if y == z:
  185.                 ans += (((count[y]*(count[y]-1))//2) * count[x])
  186.                 continue
  187.             ans += (count[x] * count[y] * count[z])
  188.         except:
  189.             pass
  190.     print(ans)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement