Problem:


Score : 400 points

Problem Statement

You are given an integer N. Among the divisors of N! (= 1 \times 2 \times ... \times N), how many Shichi-Go numbers (literally "Seven-Five numbers") are there?

Here, a Shichi-Go number is a positive integer that has exactly 75 divisors.

Note

When a positive integer A divides a positive integer B, A is said to a divisor of B.
For example, 6 has four divisors: 1, 2, 3 and 6.

Constraints

1 \leq N \leq 100

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the number of the Shichi-Go numbers that are divisors of N!.

Sample Input 1

9

Sample Output 1

0

There are no Shichi-Go numbers among the divisors of 9! = 1 \times 2 \times ... \times 9 = 362880.

Sample Input 2

10

Sample Output 2

1

There is one Shichi-Go number among the divisors of 10! = 3628800: 32400.

Sample Input 3

100

Sample Output 3

543



Sample input:
9


Sample output:
0

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def factorization(n):
    arr = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt

    if temp != 1:
        arr[temp] = 1

    if arr == []:
        arr[n] = 1

    return arr


def main():
    input = stdin.buffer.readline
    n = int(input())

    mods = {}

    for i in range(1, n + 1):
        tmp = factorization(i)
        for j in tmp:
            if j in mods:
                mods[j] += tmp[j]
            else:
                mods[j] = tmp[j]

    c3 = 0
    c5 = 0
    c15 = 0
    c25 = 0
    c75 = 0

    for k in mods:
        if 3 <= mods[k] + 1 < 5:
            c3 += 1
        if 5 <= mods[k] + 1 < 15:
            c5 += 1
        if 15 <= mods[k] + 1 < 25:
            c15 += 1
        if 25 <= mods[k] + 1 < 75:
            c25 += 1
        if mods[k] + 1 >= 75:
            c75 += 1

    ans = 0
    ans += (c5 + c15 + c25 + c75) * (c5 + c15 + c25 + c75 - 1) // 2 * (c3 + c5 + c15 + c25 + c75 - 2)
    ans += (c15 + c25 + c75) * (c5 + c15 + c25 + c75 - 1)
    ans += (c25 + c75) * (c3 + c5 + c15 + c25 + c75 - 1)
    ans += c75

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
n = int(input())

prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
dic = {}
for num in prime:
    dic[num] = 0
for i in range(1, n + 1):
    j = i
    for num in dic:
        if j == 1:
            break
        while j % num == 0:
            j //= num
            dic[num] += 1
        
        
more_2 = 0
more_4 = 0
more_14 = 0
more_24 = 0
more_74 = 0
for _, j in dic.items():
    if j >= 2:
        more_2 += 1
    if j >= 4:
        more_4 += 1
    if j >= 14:
        more_14 += 1
    if j >= 24:
        more_24 += 1
    if j >= 74:
        more_74 += 1
ans = 0
if more_24 >= 1:
    ans += more_24 * (more_2 - 1)
if more_14 >= 1:
    ans += more_14 * (more_4 - 1)
if more_4 >= 2:
    ans += (more_4 * (more_4 - 1) * (more_2 - 2)) // 2
if more_74 >= 1:
    ans += more_74
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce


def solve(N):
    if N <= 1:
        return 0
    primes = [
        2, 3, 5, 7, 11,
        13, 17, 19, 23, 29,
        31, 37, 41, 43, 47,
        53, 59, 61, 67, 71,
        73, 79, 83, 89, 97,
    ]
    primes = [p for p in primes if p <= N]
    exps = [0] * len(primes)
    for i in range(len(primes)):
        p = primes[i]
        pi = p
        while pi <= N:
            exps[i] += N // pi
            pi *= p

    ans = 0
    for i in range(len(exps)):
        a = exps[i]

        if 74 <= a:  # 75
            ans += 1

        for j in range(i + 1, len(exps)):
            b = exps[j]

            if 24 <= a and 2 <= b:  # 25*3
                ans += 1
            if 24 <= b:  # 3*25
                ans += 1

            if 14 <= a and 4 <= b:  # 15*5
                ans += 1
            if 14 <= b:  # 5*15
                ans += 1

            for k in range(j + 1, len(exps)):
                c = exps[k]

                if 4 <= c:  # 3*5*5 or 5*3*3
                    ans += 2
                if 4 <= b and 2 <= c:  # 5*5*3
                    ans += 1

    return ans


N = int(input())
print(solve(N))

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict

N = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

primes = []
for i in range(2, N + 1):
    primes += prime_factorize(i)

counters = Counter(primes)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

divisors = make_divisors(75)
cnt = defaultdict(int)
for k, v in counters.items():
    for d in divisors:
        if v + 1 >= d:
            cnt[d] += 1     
print(cnt[75] + cnt[25] * (cnt[3] - 1) + cnt[15] * (cnt[5] - 1)
+ max(cnt[5] * (cnt[5] - 1) * (cnt[3] - 2) // 2, 0))

Submission status: Accepted

Solution code:
import collections

n = int(input())


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


x = 1

for i in range(1, n+1):
    x *= i

p = collections.Counter(prime_factorize(x))

q = list(p.values())
ans = 0

ans += sum(1 for i in q if i >= 74)

for i in range(len(q)):
    for j in range(len(q)):
        if i == j:
            continue
        if q[i] >= 4 and q[j] >= 14:
            ans += 1
        if q[i] >= 2 and q[j] >= 24:
            ans += 1

for i in range(len(q)):
    for j in range(i + 1, len(q)):
        for k in range(len(q)):
            if i == k or j == k:
                continue
            if q[i] >= 4 and q[j] >= 4 and q[k] >= 2:
                ans += 1

print(ans)

Submission status: Accepted

Solution code:
# D - 756
from collections import defaultdict

N = int(input())

def prime_factorization(n):
    prime_factors = []
    if n < 2:
        return 0
    for i in range(2, int(pow(n, 0.5)+1)):
        if n%i==0:
            ex = 0
            while n%i==0:
                ex += 1
                n //= i
            prime_factors.append((i, ex))
    # 割り切れなかった残りのnが1でない(素数)場合、リストに加える
    if n!=1:
        prime_factors.append((n,1))
    return prime_factors

primes = defaultdict(int)
for i in range(2, N+1):
    p = prime_factorization(i)
    for (j, k) in p:
        primes[j] += k

primes = list(primes.values())
l = len(primes)

ans = 0
arr = []
def dfs(n, x, s):
    global ans
    if x == l:
        if s == 75:
            ans += 1
        return
    for i in range(min(primes[x]+1, 75//s)):
        if i in (0, 2, 4, 14, 24, 74):
            n.append(i)
            dfs(n, x+1, s*(i+1))
            n.pop()
    return

dfs(arr, 0, 1)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def Yes(): print("Yes"); return
def No(): print("No"); return

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############


#####約数列挙#####

N = inputI()

dic = {}
for i in range(2,N+1):
  for p,n in factorization(i):
    if p in dic:
      dic[p] += n
    else:
      dic[p] = n

key = [k for k in dic]


ans = 0
for p in key:
  if dic[p] >= 74:
    ans += 1
    
for p in key:
  if dic[p] >= 24:
    for q in key:
      if dic[q] >= 2 and p!=q:
        ans += 1

for p in key:
  if dic[p] >= 14:
    for q in key:
      if dic[q] >= 4 and p!=q:
        ans += 1
        
for p in key:
  for q in key:
    if p > q and dic[p] >= 4 and dic[q] >= 4:
      for r in key:
        if dic[r] >= 2 and p!=r and q!=r:
            ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
def fact(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

from collections import defaultdict
d = defaultdict(int)
for i in range(1,n+1):
    for itm in fact(i):
        if itm[0]!=1:
            d[itm[0]]+=itm[1]
keys = d.keys()
a=0
for p in keys:
    if d[p]>=74:
        a+=1
    for q in keys:
        if p==q:
            continue
        if d[p] >=2 and d[q]>=24:
            a+=1
        if d[p] >=4 and d[q]>=14:
            a+=1
        for r in keys:
            if q==r or r==p:
                continue
            if d[p] >=2 and d[q]>=4 and d[r]>=4:
                a+=0.5

print(int(a))

Submission status: Accepted

Solution code:
def prime_factor(n):
    factors = [0] * (n+1)
    for i in range(2, int(n**0.5)+1):
        count = 0
        while n % i == 0:
            count += 1
            n //= i
        if count != 0:
            factors[i] = count
    if n != 1:
        factors[n] = 1
    return factors

n = int(input())
nl = [0] * (n+1)
for i in range(1, n + 1):
    l = prime_factor(i)
    for i, num in enumerate(l):
        nl[i] += num
over4 = 0
over2 = 0
over74 = 0
over14 = 0
over24 = 0
for i in nl:
    if i >= 74:
        over74 += 1
    if i >= 24:
        over24 += 1
    if i >= 14:
        over14 += 1
    if i >= 4:
        over4 += 1
    if i >= 2:
        over2 += 1
cnt = 0
cnt += over4*(over4-1)/2*(over2-2)
cnt += over24*(over2-1)
cnt += over14*(over4-1)
cnt += over74
print(int(cnt))

Submission status: Accepted

Solution code:
import math
n = int(input())
lis = [0] * n
for i in range(2,n+1):
    now = i
    for j in range(2,math.ceil(math.sqrt(i))+1):
        while now % j == 0:
            now //= j
            lis[j-1] += 1
    if now != 1:
        lis[now-1] += 1

def num(l):
    return len(list(filter(lambda x: x >= l-1, lis)))

print(num(75) + num(25) * (num(3) -1) + num(15) * (num(5) - 1) + num(5) * (num(5) - 1) * (num(3) - 2) // 2)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
import itertools
def trial_division(n):
    a = [1]
    for i in range(2,int(math.sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            a.append(i)
    a.append(n)
    return a

N = int(input())
d = defaultdict(int)
for i in range(2,N+1):
    for k in trial_division(i):
        if k != 1:
            d[k] += 1
check = []
for v in d.values():
    if v != 1:
        check.append(v)
M = len(check)
tmp = 1
ans = 0

for i in check:
    if i >= 74:
        ans += 1

for i in range(M):
    for k in range(i+1,M):
        for a in range(1,check[i]+1):
            for b in range(1,check[k]+1):
                if (a+1)*(b+1) == 75:
                    ans += 1

for i in range(M):
    for k in range(i+1,M):
        for l in range(k+1,M):
            for a in range(1,check[i]+1):
                for b in range(1,check[k]+1):
                    for c in range(1,check[l]+1):
                        if (a+1)*(b+1)*(c+1) == 75:
                            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

N = int(readline())
e = [0] * (N+1)

for i in range(2, N+1):
    cur = i
    for j in range(2, i+1):
        while cur % j == 0:
            e[j] += 1
            cur //= j

def num(m):
    # e の要素のうち、m-1 以上のものの個数
    return len([1 for x in e if x >= m-1])
    # return len(list(filter(lambda x: x >= m-1, e)))

def main():
    print(num(75) + num(25) * (num(3) - 1) + num(15) * (num(5) - 1) 
    + num(5) * (num(5) - 1) * (num(3) - 2) // 2)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

sieve = [0] * 101
sieve[0] = -1
sieve[1] = -1
for i in range(2, 101):
    if sieve[i] != 0:
        continue
    sieve[i] = i
    for j in range(i * i, 101, i):
        if sieve[j] == 0:
            sieve[j] = i

d = {}
for i in range(2, N + 1):
    while i != 1:
        d.setdefault(sieve[i], 0)
        d[sieve[i]] += 1
        i //= sieve[i]


result = 0
# 75 = 5 * 5 * 3
# x ^ 4 * y ^ 4 * z ^ 2 の約数の個数は75個
n2 = 0
n4 = 0
for k in d:
    if 2 <= d[k] <= 3:
        n2 += 1
    elif d[k] >= 4:
        n4 += 1
result += n2 * n4 * (n4 - 1) // 2 + n4 * (n4 - 1) * (n4 - 2) // 2
# x ^ 14 * y ^ 4 の約数の個数は75個
n4 = 0
n14 = 0
for k in d:
    if 4 <= d[k] <= 13:
        n4 += 1
    elif d[k] >= 14:
        n14 += 1
result += n4 * n14 + n14 * (n14 - 1)
# x ^ 24 * y ^ 2 の約数の個数は75個
n2 = 0
n24 = 0
for k in d:
    if 2 <= d[k] <= 23:
        n2 += 1
    elif d[k] >= 24:
        n24 += 1
result += n2 * n24 + n24 * (n24 - 1)
# x ^ 74 の約数の個数は75個
n74 = 0
for k in d:
    if d[k] >= 74:
        n74 += 1
result += n74
print(result)

Submission status: Accepted

Solution code:
N = int(input())

sieve = [0] * 101
sieve[0] = -1
sieve[1] = -1
for i in range(2, 101):
    if sieve[i] != 0:
        continue
    sieve[i] = i
    for j in range(i * i, 101, i):
        if sieve[j] == 0:
            sieve[j] = i

d = {}
for i in range(2, N + 1):
    while i != 1:
        d.setdefault(sieve[i], 0)
        d[sieve[i]] += 1
        i //= sieve[i]

# 75 = 5 * 5 * 3
#    = 15 * 5
#    = 25 * 3
#    = 75
n74 = 0
n24 = 0
n14 = 0
n4 = 0
n2 = 0
for k in d:
    if d[k] >= 74:
        n74 += 1
    if d[k] >= 24:
        n24 += 1
    if d[k] >= 14:
        n14 += 1
    if d[k] >= 4:
        n4 += 1
    if d[k] >= 2:
        n2 += 1

result = 0
# x ^ 4 * y ^ 4 * z ^ 2 の約数の個数は75個
result += n4 * (n4 - 1) // 2 * (n2 - 2)
# x ^ 14 * y ^ 4 の約数の個数は75個
result += n14 * (n4 - 1)
# x ^ 24 * y ^ 2 の約数の個数は75個
result += n24 * (n2 - 1)
# x ^ 74 の約数の個数は75個
result += n74
print(result)

Submission status: Accepted

Solution code:
def f(n):
    # prime factorization of n!
    pf = [0 for _ in range(n + 1)]
    for i in range(2, n + 1):
        cur = i
        for j in range(2, i + 1):
            while cur % j == 0:
                pf[j] += 1
                cur //= j
    return pf


def num(m, pf):
    return len(list(filter(lambda x: x >= m - 1, pf)))


def main():
    N = int(input())
    pf = f(N)
    ans = num(75, pf)
    ans += num(25, pf) * (num(3, pf) - 1)
    ans += num(15, pf) * (num(5, pf) - 1)
    ans += num(5, pf) * (num(5, pf) - 1) * (num(3, pf) - 2) // 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    class Eratos:
        def __init__(self, num):
            '''
            O(nlglgn) で num までの素数判定テーブルを作る
            >>> e = Eratos(10)
            >>> e.table
            [False, False, True, True, False, True, False, True, False, False, False]
            '''
            assert(num >= 1)
            self.table_max = num
            # self.table[i] は i が素数かどうかを示す (bool)
            self.table = [False if i == 0 or i == 1 else True for i in range(num+1)]
            for i in range(2, int(math.sqrt(num)) + 1):
                if self.table[i]:
                    for j in range(i ** 2, num + 1, i):    # i**2 からスタートすることで定数倍高速化できる
                        self.table[j] = False
        
        def is_prime(self, num):
            '''
            O(1) で素数判定を行う
            >>> e = Eratos(100)
            >>> [i for i in range(1, 101) if e.is_prime(i)]
            [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
            '''
            assert(num >= 1)
            if num > self.table_max:
                raise ValueError('Eratos.is_prime(): exceed table_max({}). got {}'.format(self.table_max, num))
            return self.table[num]
        
        def prime_factorize(self, num):
            '''
            O(√n) で素因数分解を行う
            >>> e = Eratos(10000)
            >>> e.prime_factorize(6552)
            {2: 3, 3: 2, 7: 1, 13: 1}
            '''
            assert(num >= 1)
            if int(math.sqrt(num)) > self.table_max:
                raise ValueError('Eratos.prime_factorize(): exceed prime table size. got {}'.format(num))
            # 素因数分解の結果を記録する辞書        
            factorized_dict = dict()
            candidate_prime_numbers = [i for i in range(2, int(math.sqrt(num)) + 1) if self.is_prime(i)]
            # n について、√n 以下の素数で割り続けると最後には 1 or 素数となる
            # 背理法を考えれば自明 (残された数が √n より上の素数の積であると仮定。これは自明に n を超えるため矛盾)
            for p in candidate_prime_numbers:
                if num == 1:    # これ以上調査は無意味
                    break
                if num % p == 0:
                    cnt = 0
                    while num % p == 0:
                        num //= p
                        cnt += 1
                    factorized_dict[p] = cnt
            if num != 1:
                factorized_dict[num] = 1
            return factorized_dict
        
        def enum_divisor(self, num):
            '''
            O(√n) で約数列挙を行う
            >>> e = Eratos(10000)
            >>> e.enum_divisor(4)
            [1, 2, 4]
            >>> e.enum_divisor(19)
            [1, 19]
            >>> e.enum_divisor(100)
            [1, 2, 4, 5, 10, 20, 25, 50, 100]
            '''
            divisor_small = []
            divisor_large = []
            for i in range(1, int(math.sqrt(num)) + 1):
                if num % i == 0:
                    divisor_small.append(i)
                    if i != num // i:
                        divisor_large.append(num // i)
            divisor_large.reverse()
            return divisor_small + divisor_large
    
    n = ii()
    e = Eratos(n)
    c = Counter()
    for i in range(2, n + 1):
        c += Counter(e.prime_factorize(i))
    # print(c)
    
    gt_74_candidate = 0
    gt_24_candidate = 0
    gt_14_candidate = 0
    gt_4_candidate = 0
    gt_2_candidate = 0
    for _, v in c.items():
        if v >= 2:
            gt_2_candidate += 1
        if v >= 4:
            gt_4_candidate += 1
        if v >= 14:
            gt_14_candidate += 1
        if v >= 24:
            gt_24_candidate += 1
        if v >= 74:
            gt_74_candidate += 1
    
    def calc_3_5_5(a, b):
        if a >= 3 and b >= 2:
            # bC2 * (a - 2)
            return (b * (b-1) // 2) * (a - 2)
        else:
            return 0
    
    def calc_5_15(a, b):
        if a >= 2 and b >= 1:
            # bC1 * (a - 1)
            return b * (a - 1)
        else:
            return 0
    
    def calc_3_25(a, b):
        if a >= 2 and b >= 1:
            # bC1 * (a - 1)
            return b * (a - 1)
        else:
            return 0
    
    def calc_75(a):
        if a >= 1:
            return a
        else:
            return 0


    def calc_all_75_num(gt_2_candidate, gt_4_candidate, gt_14_candidate, gt_24_candidate, gt_74_candidate):
        ans = 0
        ans += calc_3_5_5(gt_2_candidate, gt_4_candidate)
        # print(ans)
        ans += calc_5_15(gt_4_candidate, gt_14_candidate)
        # print(ans)
        ans += calc_3_25(gt_2_candidate, gt_24_candidate)
        # print(ans)
        ans += calc_75(gt_74_candidate)
        # print(ans)
        return ans
    
    print(calc_all_75_num(gt_2_candidate, gt_4_candidate, gt_14_candidate, gt_24_candidate, gt_74_candidate))



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
prime = [2]
for i in range(3,n+1,2):
  for j in prime:
    if i % j == 0:
      break
    elif i**0.5 < j:
      prime.append(i)
      break
di = dict(zip(prime,[0]*len(prime)))
for i in range(1,n+1):
  for j in prime:
    if i == 1:
      break
    c = 0
    while i % j == 0:
      i = i//j
      c += 1
    di[j] += c
a = len([i for i in di.values() if i >= 74])
b = len([i for i in di.values() if i >= 24])
c = len([i for i in di.values() if i >= 14])
d = len([i for i in di.values() if i >= 4])
e = len([i for i in di.values() if i >= 2])
print(a + b*(e-1) + c*(d-1) + d*(d-1)*(e-2)//2)

Submission status: Accepted

Solution code:

def prime_factor(n):
    ass = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass


n = int(input())
n_prime = {}
for i in range(1, n+1):
    for item in prime_factor(i):
        if item not in n_prime.keys():
            n_prime[item] = 0
        n_prime[item] += 1
#print(n_prime)
count_74 = 0
count_24 = 0
count_14 = 0
count_4 = 0
count_2 = 0
for prime, count in n_prime.items():
    if count >= 74:
        count_74 += 1
    if count >= 24:
        count_24 += 1
    if count >= 14:
        count_14 += 1
    if count >= 4:
        count_4 += 1
    if count >= 2:
        count_2 += 1
ans75 = count_74
ans25 = count_24*(count_2 - 1)
ans15 = count_14*(count_4 - 1)
ans5 = count_4*(count_4 - 1)*(count_2 - 2)//2
print(ans75 + ans25 + ans15 + ans5)

Submission status: Accepted

Solution code:
from collections import Counter


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


n = int(input())
c = Counter()

for i in range(2, n+1):
    c.update(prime_factorize(i))

d = {2: 0, 4: 0, 14: 0, 24: 0, 74: 0}
for k, v in c.items():
    for size in [2, 4, 14, 24, 74]:
        if v >= size:
            d[size] += 1

total = 0
if d[4] >= 2 and d[2] >= 3:
    total += d[4] * (d[4] - 1) // 2 * (d[2] - 2)

if d[14] >= 1 and d[4] >= 2:
    total += d[14] * (d[4] - 1)

if d[24] >= 1 and d[2] >= 2:
    total += d[24] * (d[2] - 1)

if d[74] >= 1:
    total += d[74]

print(total)

Submission status: Accepted

Solution code:
import math
def firstprime(n):
  p = 2
  while(p <= math.sqrt(n)):
    if(n % p == 0):
      return p
    p += 1
  return n

N = int(input())
prime = [0] * 101
for i in range(2, N+1):
  n = i
  while(n > 1):
    p = firstprime(n)
    prime[p] += 1
    n = n // p
    
p2 = 0
p4 = 0
p14 = 0
p24 = 0
p74 = 0
for i in range(101):
  if(prime[i] >= 74):
    p74 += 1
  if(prime[i] >= 24):
    p24 += 1
  if(prime[i] >= 14):
    p14 += 1
  if(prime[i] >= 4):
    p4 += 1
  if(prime[i] >= 2):
    p2 += 1
p3_5_5 = p4*(p4-1)*(p2-2)//2
p5_15 = p14*(p4-1)
p3_25 = p24*(p2-1)
p75 = p74
print(p3_5_5+p5_15+p3_25+p75)

Submission status: Accepted

Solution code:
import itertools
from collections import Counter
from math import factorial

N = int(input())


def factorization(n):
    arr = dict()
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt

    if temp != 1:
        arr[temp] = 1

    if not arr and n != 1:
        arr[n] = 1

    return arr


ans = 0
ct = Counter()
for i in range(2, N + 1):
    ct += Counter(factorization(i))


def solve(*exps):
    ret = 0
    for t in itertools.permutations(ct.values(), len(exps)):
        if all(t[i] - exps[i] >= 0 for i in range(len(exps))):
            ret += 1
    for x in Counter(exps).values():
        ret //= factorial(x)
    return ret


print(solve(2, 4, 4) + solve(14, 4) + solve(24, 2) + solve(74))

Submission status: Accepted

Solution code:
n=int(input())

l=[0]*(n+1)
p=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
for i in p:
    temp=n
    while temp>=i:
        temp//=i
        l[i]+=temp
var=sorted([g for g in l if g])
ans=sum(int(x>=74)for x in var)
lo=len(var)
for a,b in [(3,25),(5,15)]:
    for i in range(lo):
        for j in range(lo):
            if i!=j and a-1<=var[i]and b-1<=var[j]:
                ans+=1
for i in range(lo):
    for j in range(lo):
        for k in range(j+1,lo):
            if i!=j and k!=i and var[i]>=2 and var[j]>=4 and var[k]>=4:
                ans+=1
print(ans)

Submission status: Accepted

Solution code:
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    N = int(input())
    h = list(map(int, input().split()))

    import math

    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f

    def make_prime_list_2(num):
        if num < 2:
            return []

        # 0のものは素数じゃないとする
        prime_list = [i for i in range(num + 1)]
        prime_list[1] = 0  # 1は素数ではない
        num_sqrt = math.sqrt(num)

        for prime in prime_list:
            if prime == 0:
                continue
            if prime > num_sqrt:
                break

            for non_prime in range(2 * prime, num, prime):
                prime_list[non_prime] = 0

        return [prime for prime in prime_list if prime != 0]

    def prime_factorization_2(num, dict_counter):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""

        if num <= 1:
            # 例えば1を食ったときの対処の仕方は問題によって違うと思うのでそのつど考える。
            # cf. https://atcoder.jp/contests/abc110/submissions/12688244
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)

            # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452

            for prime in prime_list:
                while num % prime == 0:
                    if prime in dict_counter:
                        dict_counter[prime] += 1
                    else:
                        dict_counter[prime] = 1
                    num //= prime
            if num != 1:
                if num in dict_counter:
                    dict_counter[num] += 1
                else:
                    dict_counter[num] = 1

            return dict_counter
    dict_counter = {}
    for i in range(1, N+1):
        prime_factorization_2(i, dict_counter)

    l = list(dict_counter.values())
    ll = len(l)
    
    cnts={2:0,4:0,14:0,24:0,74:0}

    cnt=0
    for i in l:
        if i>=2:
            cnts[2]+=1
        if i>=4:
            cnts[4]+=1
        if i>=14:
            cnts[14]+=1
        if i>=24:
            cnts[24]+=1
        if i>=74:
            cnts[74]+=1
    ans=0
    ans+=cnts[4]*(cnts[4]-1)//2*(cnts[2]-2)
    ans+=cnts[14]*(cnts[4]-1)+cnts[24]*(cnts[2]-1)
    ans+=cnts[74]
    print(ans)
                


    


resolve()