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 collections import Counter
N = int(input())


# 素因数分解
def prime_factorization(n):
    table = []
    for x in range(2, int(n**0.5)+1):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table


T = []
for i in range(2, N + 1):
    T.extend(prime_factorization(i))

C = list(Counter(T).values())


def num(x):
    return len([n for n in C if n >= x - 1])


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

Submission status: Accepted

Solution code:
N = int(input())
d = {}
for i in range(2, N + 1):
	m = i
	for j in range(2, i + 1):
		if m == 1:
			break
		while m % j == 0:
			if j in d:
				d[j] = d[j] + 1
			else:
				d[j] = 1
			m = m / j
l = [3, 5, 15, 25, 75]
e = {}
for i in l:
	e[i] = 0
for i in d:
	for j in l:
		if d[i] > j - 2:
			e[j] += 1
ans = 0
if e[5] > 1 and e[3] > 2:
	ans = int(e[5] * (e[5] - 1) / 2 * (e[3] - 2))
if e[3] > 1 and e[25] > 0:
	ans += e[25] * (e[3] - 1)
if e[5] > 1 and e[15] > 0:
	ans += e[15] * (e[5] - 1)
if e[75] > 0:
	ans += e[75]
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections
from collections import Counter
# from collections import deque
# from collections import defaultdict
import itertools
# from itertools import accumulate
# from itertools import permutations
# from itertools import combinations
# from itertools import takewhile
# from itertools import compress
# import functools
# from functools import reduce
import math
# from math import gcd
# from math import inf
# from math import ceil
# from math import floor
# from math import log10
# from math import log2
# from math import log
from math import factorial

# import re

N = int(input())


def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table


P = prime_decomposition(factorial(N))
C = Counter(P)

n2, n4, n14, n24, n74 = [0] * 5

for k, v in C.items():
    n2 += 1 if v >= 2 else 0
    n4 += 1 if v >= 4 else 0
    n14 += 1 if v >= 14 else 0
    n24 += 1 if v >= 24 else 0
    n74 += 1 if v >= 74 else 0

p1, p2, p3, p4 = [0] * 4
p1 = n4 * (n4 - 1) * (n2 - 2) // 2
p2 = n14 * (n4 - 1)
p3 = n74
p4 = n24 * (n2 - 1)

print(sum([p1, p2, p3, p4]))

Submission status: Accepted

Solution code:
import collections

n = int(input())

# 75 = 3*5*5 or 3*25 or 5*15 or 75
seed_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]

d = collections.defaultdict(lambda: 0)

def bunkai(n):
    if n == 1:
        return 0
    else:
        for i in seed_primes:
            if n % i == 0:
                d[i] += 1
                return bunkai(n//i)


for i in range(1, n+1):
    bunkai(i)

tot = 0
s = 0
dd = collections.defaultdict(lambda: 0)
for v in d.values():
    if v >= 74:
        dd[74] += 1
        s += 1
    elif v >= 24:
        dd[24] += 1
        s += 1
    elif v >= 14:
        dd[14] += 1
        s += 1
    elif v >= 4:
        dd[4] += 1
        s += 1
    elif v >= 2:
        dd[2] += 1
        s += 1


#74
tot += dd[74]
#24*2
tot += (dd[74]+dd[24])*(s-1)
#14*4
tot += (dd[74]+dd[24]+dd[14])*(s-dd[2]-1)
#4*4*2
tot += int((dd[74]+dd[24]+dd[14]+dd[4])*(dd[74]+dd[24]+dd[14]+dd[4]-1)*(s-2)/2)

print(tot)

Submission status: Accepted

Solution code:
N = int(input())
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):
    return len(list(filter(lambda x: x >=m-1,e)))
    
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:
N = int(input())

s = [0] * (N+1)

for j in range(1, N+1):
    now = j

    for i in range(2, N+1):
        if now==1:
            break
        else:
            while now%i==0:
                now = now//i
                s[i] = s[i]+1
                
s2 = 0
s4 = 0
s14 = 0
s24 = 0
s74 = 0
                
for i in range(N+1):
    if s[i]>=2:
        s2 = s2+1
    if s[i]>=4:
        s4 = s4+1
    if s[i]>=14:
        s14 = s14+1
    if s[i]>=24:
        s24 = s24+1
    if s[i]>=74:
        s74 = s74+1

A = s74
B = max(0, s24*(s2-1))
C = max(0, s14*(s4-1))
D = max(0, s4*(s4-1)*(s2-2)//2)

print(A+B+C+D)

Submission status: Accepted

Solution code:
def solve(n):
    p = {}
    for m in range(1,n+1):
        for q in range(2,m+1):
            while m % q == 0:
                if not q in p:
                    p[q] = 0
                p[q] += 1
                m /= q
    S = set()
    # 5 x 5 x 3
    for k1, v1 in p.items():
        for k2, v2 in p.items():
            for k3, v3 in p.items():
                if (v1 >= 2) and (v2 >= 4) and (v3 >= 4) and (k1 != k2) and (k2 != k3) and (k1 != k3):
                    S.add((k1**2) * (k2**4) * (k3**4))
    # 25 x 3
    for k1, v1 in p.items():
        for k2, v2 in p.items():
            if (v1 >= 24) and (v2 >= 2) and (k1 != k2):
                S.add((k1**24) * (k2**2))
    # 15 x 5
    for k1, v1 in p.items():
        for k2, v2 in p.items():
            if (v1 >= 14) and (v2 >= 4) and (k1 != k2):
                S.add((k1**14) * (k2**4))
    # 75
    for k1, v1 in p.items():
        if (v1 >= 74):
            S.add(v1**74)
    return len(S)
print solve(input())

Submission status: Accepted

Solution code:
from itertools import combinations,permutations

N = int(input())

p_dic={}

for i in range(2,N+1):
    p=2
    while i!=1:
        c=0
        while i%p==0:
            c+=1
            i//=p
        if c>0 and p not in p_dic.keys():
            p_dic[p]=c
        elif c>0:
            p_dic[p]+=c
        p+=1

ans=0

p_keys = p_dic.keys()

for p in p_keys:
    if p_dic[p]>=74:
        ans+=1

for p,q in permutations(p_keys,2):
    i=p_dic[p]
    j=p_dic[q]
    if i>=2 and j>=24:
        ans+=1
    if i>=4 and j>=14:
        ans+=1

for p,q,r in combinations(p_keys,3):
    i,j,k = sorted([p_dic[p],p_dic[q],p_dic[r]])
    if i>=4:
        ans+=3
    elif j>=4 and i>=2:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
primeCounter = [0 for _ in range(N + 1)]
for i in range(2, N + 1):
    for div in range(2, i + 1):
        while i % div == 0:
            primeCounter[div] += 1
            i /= div
ans = 0
ans += len([i for i in primeCounter if i >= 74])
ans += len([i for i in primeCounter if i >= 24]) * (len([i for i in primeCounter if i >= 2]) - 1)
ans += len([i for i in primeCounter if i >= 14]) * (len([i for i in primeCounter if i >= 4]) - 1)
ans += len([i for i in primeCounter if i >= 4]) * (len([i for i in primeCounter if i >= 4]) - 1) * (len([i for i in primeCounter if i >= 2]) - 2) // 2
print(ans)

Submission status: Accepted

Solution code:
N=input()
Ans=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 8, 8, 11, 11, 11, 11, 14, 14, 32, 32, 35, 35, 35, 35, 42, 42, 42, 42, 49, 49, 49, 49, 49, 49, 75, 75, 86, 86, 86, 86, 86, 86, 123, 123, 131, 131, 131, 131, 148, 148, 153, 153, 170, 170, 170, 170, 170, 170, 227, 227, 227, 227, 227, 227, 250, 250, 323, 323, 324, 324, 324, 324, 354, 354, 354, 354, 384, 384, 384, 384, 384, 391, 491, 491, 529, 529, 529, 529, 529, 529, 543]

print Ans[N]

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline().strip())

def f1(p, k):
  # k以下のpの個数（重複あり）
  u = p
  ans = 0
  while u < k:
    ans += k//u
    u = u*p
  return ans

def f2(p, k):
  # k以下のpの個数
  u = p
  ans = {}
  r = 1
  while u < k:
    ans[r] = k//u
    u = u*p
    r = r+1
  return ans

ps = []
for x in range(2, N+1):
  primeflag = True
  for p in ps:
    if (x % p) == 0:
      primeflag = False
      break
  if primeflag == True:
    ps.append(x)

# print(ps)
# 75 = 3 * 5 * 5
# よって75数としてありうる、m = p1^q1 * .. * p_{l_m}^q_{l_m}
# qの組は、(2,4,4), (2,24), (4,14), (74)
# qに対してpの条件は、N以下のpの倍数
# （p^(2以上)があれば重複してカウント）が延べでq以上あること
# q = 74はない

ps_lim = {p: f1(p, N) for p in ps}

ps_2 = [p for p in ps if ps_lim[p] >= 2]
ps_4 = [p for p in ps if ps_lim[p] >= 4]
ps_14 = [p for p in ps if ps_lim[p] >= 14]
ps_24 = [p for p in ps if ps_lim[p] >= 24]
ps_74 = [p for p in ps if ps_lim[p] >= 74]


# 2,4,4の組
sum1 = len(ps_4) * (len(ps_4) - 1) * (len(ps_2) - 2) // 2
# 2, 24の組
sum2 = len(ps_24) * (len(ps_2) - 1)
# 4, 14の組
sum3 = len(ps_14) * (len(ps_4) - 1)
# 74
sum4 = len(ps_74)
sum = sum1 + sum2 + sum3 + sum4

print(sum)

Submission status: Accepted

Solution code:
N = int(input())
s_list = [[5, 5, 3], [25, 3], [15, 5], [75]]

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

def div_c(n):
    return len(list(filter(lambda x: x >= n-1, a))) 
    
ans=0
for s in s_list:
    i=0
    c=1
    for t in s:
        c*=(div_c(t)-i)
        i+=1
    ans+=int(c/(len(s)-len(set(s))+1))

       
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
prime = [2]
for i in range(3, 100):
    flag = 0
    for j in prime:
        if i % j == 0:
            flag = 1
    if flag == 0:
        prime.append(i)

factorization = [0 for i in range(101)]

for i in range(1, N+1):
    for j in prime:
        while i % j == 0:
            i = i // j
            factorization[j] += 1

ans = 0
factorization.sort(reverse = True)
for i in range(N):
    if factorization[i] >= 74:
        ans += 1
    else:
        break
for i in range(N):
    if factorization[i] >= 24:
        for j in range(N):
            if i != j:
                if factorization[j] >= 2:
                    ans += 1
                else:
                    break
    else:
        break

for i in range(N):
    if factorization[i] >= 14:
        for j in range(N):
            if j != i:
                if factorization[j] >= 4:
                    ans += 1
                else:
                    break
    else:
        break

for i in range(N):
    if factorization[i] >= 4:
        for j in range(i+1, N):
            if factorization[j] >= 4:
                for k in range(N):
                    if k != i and k != j:
                        if factorization[k] >= 2:
                            ans += 1
                        else:
                            break
            else:
                break
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
import copy

def fact(n,s):
    return len(list(filter(lambda x:x>=n-1,s)))


n=int(input())
s=[0]*(n+1)
for i in range(2,n+1):
    a=copy.deepcopy(i)
    for j in range(2,a+1):
        while a%j==0:
            s[j]+=1
            a//=j
#print(s)
b=fact(5,s)
print(max(0,fact(75,s)+fact(25,s)*(fact(3,s)-1)+fact(15,s)*(fact(5,s)-1)+b*(b-1)*(fact(3,s)-2)//2))

Submission status: Accepted

Solution code:
N = int(input())
import itertools

def divisor_pl(num):
    l = []
    i = 2
    while num > 1:
        if num%i == 0:
            l.append(i)
            num = int(num/i)
        else:
            i += 1
    if num != 1:
        l.append(num)
    return l

l = []
for i in range(2,N+1):
    l.append(divisor_pl(i))
l = sum(l,[])
l.sort()

fac_dict = {}
fac_list = []
for key, value in itertools.groupby(l):
    fac_dict[str(key)] = len(list(value))
    fac_list.append(key)

count = 0
#(4,4,2)型のカウント
for l in itertools.combinations(fac_list,3):
    for i in range(3):
        if fac_dict[str(l[i%3])] >= 4 and fac_dict[str(l[(i+1)%3])] >= 4 and fac_dict[str(l[(i+2)%3])] >= 2:
            count+=1

#(14,4)型のカウント
for l in itertools.combinations(fac_list,2):
    for i in range(2):
        if fac_dict[str(l[i%2])] >= 14 and fac_dict[str(l[(i+1)%2])] >= 4:
            count+=1

#(24,2)型のカウント
for l in itertools.combinations(fac_list,2):
    for i in range(2):
        if fac_dict[str(l[i%2])] >= 24 and fac_dict[str(l[(i+1)%2])] >= 2:
            count+=1

#(74)型のカウント
for l in fac_list:
    if fac_dict[str(l)] >= 74:
        count += 1

print(count)

Submission status: Accepted

Solution code:
N = int(input())
import itertools

def divisor_pl(num):
    l = []
    i = 2
    while num > 1:
        if num%i == 0:
            l.append(i)
            num = int(num/i)
            i = 2
        else:
            i += 1
    if num != 1:
        l.append(num)
    return l

l = []
for i in range(2,N+1):
    l.append(divisor_pl(i))
l = sum(l,[])
l.sort()

fac_dict = {}
fac_list = []
for key, value in itertools.groupby(l):
    fac_dict[str(key)] = len(list(value))
    fac_list.append(key)

count = 0
#(4,4,2)型のカウント
for l in itertools.combinations(fac_list,3):
    for i in range(3):
        if fac_dict[str(l[i%3])] >= 4 and fac_dict[str(l[(i+1)%3])] >= 4 and fac_dict[str(l[(i+2)%3])] >= 2:
            count+=1

#(14,4)型のカウント
for l in itertools.combinations(fac_list,2):
    for i in range(2):
        if fac_dict[str(l[i%2])] >= 14 and fac_dict[str(l[(i+1)%2])] >= 4:
            count+=1

#(24,2)型のカウント
for l in itertools.combinations(fac_list,2):
    for i in range(2):
        if fac_dict[str(l[i%2])] >= 24 and fac_dict[str(l[(i+1)%2])] >= 2:
            count+=1

#(74)型のカウント
for l in fac_list:
    if fac_dict[str(l)] >= 74:
        count += 1

print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin

d_in = lambda: int(stdin.readline())  # N = d_in()

N = d_in()


def factorize(n):
    """
    素因数分解

    Return
    ------
    fct : list
        [[素因数, 指数], ...] のリスト
            [[a_1, n_1], ..., [a_i, n_i], ...]
        n = a_1**n_1 * a_2**n_2 * ...
    """
    if n == 1:
        return [(1, 1)]
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n //= b
            e += 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def Sieve_of_Eratosthenes(x):
    """
    エラトステネスの篩を用いて素数列を返す
    2以上x未満の素数列を返す
    参考URL:
    https://qiita.com/peria/items/a4ff4ddb3336f7b81d50
    """
    primes = [2*i + 1 for i in range((x + 1) // 2)]
    primes[0] = 2
    n_primes = len(primes)
    sqrt_x = int((x + 0.1) ** 0.5)
    for i in range(1, (sqrt_x + 1) // 2):
        if not primes[i]:
            continue
        p = 2 * i + 1
        for j in range(2 * i * (i + 1), n_primes, p):
            primes[j] = False
    return list(filter(lambda x: x, primes))


primes = Sieve_of_Eratosthenes(100)
factor_dict = {i: 0 for i in primes}
for i in range(2, N+1):
    fct = factorize(i)
    for f in fct:
        factor_dict[f[0]] += f[1]


factor_num_list = list(factor_dict.values())
ans = 0

over_74 = len(list(filter(lambda x: x >= 74, factor_num_list)))
ans += over_74

over_24 = len(list(filter(lambda x: x >= 24, factor_num_list)))
over_2 = len(list(filter(lambda x: x >= 2, factor_num_list)))
ans += over_24 * (over_24 - 1)
ans += over_24 * (over_2 - over_24)

over_14 = len(list(filter(lambda x: x >= 14, factor_num_list)))
over_4 = len(list(filter(lambda x: x >= 4, factor_num_list)))
ans += over_14 * (over_14 - 1)
ans += over_14 * (over_4 - over_14)

over_4 = len(list(filter(lambda x: x >= 4, factor_num_list)))
over_2 = len(list(filter(lambda x: x >= 2, factor_num_list)))
between_2_4 = over_2 - over_4
ans += over_4 * (over_4 - 1) * (over_4 - 2) // 2
ans += over_4 * (over_4 - 1) * between_2_4 // 2

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
prime_list = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
d = []
e = [0,0,0,0,0]
f = [74,24,14,4,2]
for i in prime_list:
  a = n
  b = 0
  c = 1
  while a // (i**c) > 0:
    b += a // (i**c)
    c += 1
  else:
    d.append(b)
count = 0
len_d = len(d)-1
for k in f:
  for i,j in enumerate(d):
    if j < k:
      e[count] = i
      count += 1
      break
    elif i == len_d:
      e[count] = i+1
      count += 1
      break



print(e[0]+e[1]*(e[4]-1)+e[2]*(e[3]-1)+(e[3]*(e[3]-1)//2)*(e[4]-2))

Submission status: Accepted

Solution code:
N = int(input())

e = [0] * (N+1)

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

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

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

Submission status: Accepted

Solution code:
N = int(input())
T = [1 for k in range(101)]

for M in range(2,N+1):
    k = 2
    while k*k <= M:
        if M%k == 0:
            M //= k
            T[k] += 1
        else:
            k += 1
    if M > 1:
        T[M] += 1

C = [0 for k in range(101)]
for k in range(101):
    if T[k] >= 3:
        C[3] += 1
    if T[k] >= 5:
        C[5] += 1
    if T[k] >= 15:
        C[15] += 1
    if T[k] >= 25:
        C[25] += 1
    if T[k] >= 75:
        C[75] += 1

print(C[75] + C[25]*(C[3]-1) + C[15]*(C[5]-1) + (C[5]*(C[5]-1)*(C[3]-2))//2)

Submission status: Accepted

Solution code:
def get_primes(n):
    primes = []
    for i in range(2, n+1):
        flag = True
        for j in range(2, i+1):
            if i % j == 0 and i != j:
                flag = False
                break
        if flag:
            primes += [i]
    return primes

def main():
    n = int(input())

    primes = get_primes(n)
    cnt = len(primes)

    exps = [0] * cnt
    for i in range(2, n+1):
        k = i
        for j in range(cnt):
            while k % primes[j] == 0:
                exps[j] += 1
                k /= primes[j]

    ans = 0

    for i in range(cnt):
        if exps[i] >= 74:
            ans += 1

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

    for i in range(cnt):
        for j in range(cnt):
            for k in range(j+1, cnt):

                if i == j or i == k or j == k:
                    continue
                if exps[i] >= 2 and exps[j] >= 4 and exps[k] >= 4:
                     ans += 1

    print(ans)

main()

Submission status: Accepted

Solution code:
N = int(input())
p = [
    sum(N // (i**k) for k in range(1, 8))
    for i in range(2, 97 + 1)
    if all(i % j != 0 for j in range(2, i))
]
def f(m):
  return len([i for i in p if i >= m])
ans = f(74) + f(24) * (f(2) - 1) + f(14) * (f(4) - 1) + f(4) * (f(4) - 1) * (f(2) - 2) // 2
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

# N!を素因数分解をしたときの可能な最大値はNであることに注意
# eは0~Nまでの指数をカウントするもの
e = [0]*(N+1)

# 2からNまでそれぞれ順に素因数分解していく
for i in range(2, N+1):
    cur = i
    # 2~iまでそれぞれで割っていく
    for j in range(2, i+1):
        while cur % j == 0:
            e[j] += 1
            # curはjで割った結果になる
            cur //= j

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

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:
N = int(input())
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) :
    return len(list(filter(lambda x: x >= m-1, e)))

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:
def prime_factorization(num):
    f = 2
    factor = []
    while num > 1:
        if num % f == 0:
            factor.append(f)
            num //= f
            f = 2
        else:
            f += 1
    return {d: factor.count(d) for d in set(factor)}
N = int(input())
pff = {}
while N > 1:
    pf = prime_factorization(N)
    for k in iter(pf.keys()):
        if k in pff:
            pff[k] += pf[k]
        else:
            pff[k] = pf[k]
    N -= 1
threshold = [74, 24, 14, 4, 2]
count = [0] * len(threshold)
for i in iter(pff.values()):
    for j in range(len(threshold)):
        if i >= threshold[j]:
            count[j] += 1
ans = count[0] \
    + count[1] * (count[4] - 1) \
    + count[2] * (count[3] - 1) \
    + (count[3] * (count[3] - 1) // 2 * (count[4] - 2))
print(ans)

Submission status: Accepted

Solution code:

N = int(input())

e = [0]*(N+1)

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

def num(n):
    count = 0
    for i in range(len(e)):
        if e[i]>=n-1 :
            count += 1
    
    return count

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:
# editorialコピペ
n = int(input())
e = [0] * (n+1)
for i in range(2, n+1):
    cur=i
    for j in range(2, n+1):
        while cur % j==0:
            e[j] += 1
            cur //= j

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

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:
# -*- coding: utf-8 -*-

"""
解説参考
・まず素因数分解で階乗全部バラす
・そこからいい感じの組み合わせを探して数える
"""

N = int(input())

# 階乗の素因数分解：ひとつずつ分解したものを合算
e = [0] * (N+1)
# 階乗の各値ループ
for i in range(2, N+1):
    num = i
    # 素因数分解するループ
    for j in range(2, N+1):
        while num % j == 0:
            num //= j
            e[j] += 1

# 約数75(各指数+1をかける)を取りうる素因数の組み合わせを探していく
nums = set()
# 指数が4, 4, 2
for p in range(2, N+1):
    for q in range(2, N+1):
        for r in range(2, N+1):
            if (e[p] >= 4 and e[q] >= 4 and e[r] >= 2
                    and p != q and q != r and r != p):
                nums.add(pow(p, 4) * pow(q, 4) * pow(r, 2))
# 指数が14, 4 or 24, 2
for p in range(2, N+1):
    for q in range(2, N+1):
        if e[p] >= 14 and e[q] >= 4 and p != q:
            nums.add(pow(p, 14) * pow(q, 4))
        if e[p] >= 24 and e[q] >= 2 and p != q:
            nums.add(pow(p, 24) * pow(q, 2))
# 指数が74
for p in range(2, N+1):
    if e[p] >= 74:
        nums.add(pow(p, 74))  

print(len(nums))

Submission status: Accepted

Solution code:
N = int(input())
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):
    return len(list(filter(lambda x: x >= m-1, e)))

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

SO=[0 for i in range(101)]

N=int(input())
for i in range(2,N+1):
    NUM=i
    for j in range(2,100):
        while NUM%j==0:
            SO[j]+=1
            NUM=NUM/j
A74=0
A24=0
A14=0
A04=0
A02=0
for j in range(len(SO)):
    if SO[j]>=74:
        A74+=1
    if SO[j]>=24:
        A24+=1
    if SO[j]>=14:
        A14+=1
    if SO[j]>=4:
        A04+=1
    if SO[j]>=2:
        A02+=1
#print(SO)
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

#74
ans=A74
#3*5*5
if A04>=2:
    ans+=(A02-2)*combinations_count(A04,2)
#3*25
ans+=(A02-1)*A24
#5*15
ans+=(A04-1)*A14


print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
N = int(input())
if N == 1:
    print(0)
    exit(0)
def get_sieve_of_eratosthenes(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
    return prime
prime = get_sieve_of_eratosthenes(N)
n = len(prime)
ans = 0
divNum = [0] + [ N//i for i in range(1,N+1) ]
for p in prime:
    ip = p * p
    while ip <= N:
        divNum[p] += divNum[ip]
        ip *= p

for i in range(n):
    if 74 <= divNum[prime[i]]:
        ans += 1
    for j in range(n):
        if i != j and 4 <= divNum[prime[i]] and 14 <= divNum[prime[j]]:
            ans += 1
        if i != j and 2 <= divNum[prime[i]] and 24 <= divNum[prime[j]]:
            ans += 1
        for k in range(j+1,n):
            if i != j and i != k:
                if 2 <= divNum[prime[i]] and 4 <= divNum[prime[j]] and 4 <= divNum[prime[k]]:
                    ans += 1
            
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
e = [0] * (n+1)

for i in range(2, n + 1):
    for j in range(2, i + 1):
        while i % j == 0:
            e[j] += 1
            i //= j
            
def f(m):
    return len(list(filter(lambda x: x >= m-1, e)))

c1 = f(75)
c2 = f(25) * (f(3) - 1)
c3 = f(15) * (f(5) - 1)
c4 = f(5) * (f(5) - 1) * (f(3) - 2) // 2

print(c1 + c2 + c3 + c4)

Submission status: Accepted

Solution code:
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
c = {3:0, 5:0, 15:0, 25:0, 75:0}
n = int(input())
for p in primes:
  r = n//p
  a = 0
  while r>0:
    a += r
    r //= p
  for x in c.keys():
    if x-1 <= a:
      c[x] += 1
print(c[75]+c[25]*(c[3]-1)+c[15]*(c[5]-1)+c[5]*(c[5]-1)*(c[3]-2)//2)

Submission status: Accepted

Solution code:
N = int(input()) 
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):
    return len(list(filter(lambda x: x >= m-1, e)))
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:
from collections import defaultdict
N = int(input())
D = defaultdict(int)


# 素因数分解
def prime_factorization(n):
    table = []
    for x in range(2, int(n**0.5)+2):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table


for n in range(2, N + 1):
    T = prime_factorization(n)
    for t in T:
        D[t] += 1


def num(m):
    return len([i for i in D.values() if i >= m - 1])


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

Submission status: Accepted

Solution code:
import itertools

N = int(input())

# 素数リストアップ
primes = []
for n in range(2,N+1):
    if 0 not in map(lambda m: n%m, range(2,n)):
        primes.append(n)

# N! 素因数分解
factors = [0]*len(primes)
for n in range(2,N+1):
    for i in range(len(primes)):
        p = primes[i]
        while n % p == 0 :
            n /= p
            factors[i] += 1

def count(fs):
    num = 0
    for v in itertools.permutations(factors, len(fs)):
        if False not in map(lambda i: fs[i]<=v[i]+1, range(len(v))):
            num +=1
    return num
                                    

num = 0
num += count([75])
num += count([3,25])
num += count([5,15])
num += int(count([3,5,5])/2)
print(num)

Submission status: Accepted

Solution code:
def isPrime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

N = int(input())
cnt = []

for i in range(2, N+1):
    if not isPrime(i):
        continue
    c = 0
    x = i
    while N // x > 0:
        c += N // x
        x *= i
    cnt.append(c)

ans = 0
for x in cnt:
    if x >= 74:
        ans += 1

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

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

print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())
pn = [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]

C3 = 0
C5 = 0
C15 = 0
C25 = 0
C75 = 0

for i in pn:
    if math.factorial(N) % pow(i,2) == 0:
        C3 += 1
    if math.factorial(N) % pow(i,4) == 0:
        C5 += 1
    if math.factorial(N) % pow(i,14) == 0:
        C15 += 1
    if math.factorial(N) % pow(i,24) == 0:
        C25 += 1
    if math.factorial(N) % pow(i,74) == 0:
        C75 += 1

ans = (C3-2)*C5*(C5-1)//2 + (C5-1)*C15 + (C3-1)*C25 + C75 
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
pn = [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]
ans = []

for ar in itertools.permutations(pn,3):
    if math.factorial(N) > (ar[0]**2*ar[1]**4*ar[2]**4) and\
    math.factorial(N) % (ar[0]**2*ar[1]**4*ar[2]**4) == 0:
        ans.append(ar[0]**2*ar[1]**4*ar[2]**4)

for ar in itertools.permutations(pn,2):
    if math.factorial(N) > (ar[0]**4*ar[1]**14) and\
    math.factorial(N) % (ar[0]**4*ar[1]**14) == 0:
        ans.append(ar[0]**4*ar[1]**14)

for ar in itertools.permutations(pn,2):
    if math.factorial(N) > (ar[0]**2*ar[1]**24) and\
    math.factorial(N) % (ar[0]**2*ar[1]**24) == 0:
        ans.append(ar[0]**2*ar[1]**24)

for ar in pn:
    if math.factorial(N) > ar**74 and\
    math.factorial(N) % ar**74 == 0:
        ans.append(ar**74)

ans = set(ans)
print(len(ans))

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
pn = [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]
ans = []
cnt = 0


for ar in itertools.permutations(pn,3):
    if math.factorial(N) > (ar[0]**2*ar[1]**4*ar[2]**4) and\
    math.factorial(N) % (ar[0]**2*ar[1]**4*ar[2]**4) == 0:
        ans.append(ar[0]**2*ar[1]**4*ar[2]**4)

for ar in itertools.permutations(pn,2):
    if math.factorial(N) > (ar[0]**4*ar[1]**14) and\
    math.factorial(N) % (ar[0]**4*ar[1]**14) == 0:
        ans.append(ar[0]**4*ar[1]**14)

for ar in itertools.permutations(pn,2):
    if math.factorial(N) > (ar[0]**2*ar[1]**24) and\
    math.factorial(N) % (ar[0]**2*ar[1]**24) == 0:
        ans.append(ar[0]**2*ar[1]**24)

for ar in pn:
    if math.factorial(N) > ar**74 and\
    math.factorial(N) % ar**74 == 0:
        ans.append(ar**74)

ans = set(ans)
print(len(ans))