Submission #69686654

---

Source Code Expand

import sys
input = sys.stdin.readline

def sieve(n):
  is_p = [True]*(n+1)
  is_p[0]=is_p[1]=False
  for i in range(2,int(n**0.5)+1):
    if is_p[i]:
      step = i
      s = i*i
      is_p[s:n+1:step] = [False]*(((n - s)//step) + 1)
  return [i for i,v in enumerate(is_p) if v]

def build_ep_fact(maxn, primes):
  ep = {}
  for p in primes:
    a = [0]*(maxn+1)
    for x in range(1, maxn+1):
      t = x
      c = 0
      while t % p == 0:
        c += 1
        t //= p
      a[x] = a[x-1] + c
    ep[p] = a
  return ep

t, mod = map(int, input().split())

primes = sieve(5005)
e = build_ep_fact(5005, primes)

print(len(primes))
for _ in range(t):
  n = int(input())
  C = list(map(int, input().split()))
  sum_ = sum(C)
  ans = 1
  for p in primes:
    if p>sum_: break
    t = e[p][sum_]
    for c in C:
      t -= e[p][c]
    ans *= pow(p, t, mod)
    ans %= mod
  print(ans)

Submission Info

Judge Result