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

Solution (Python):
from collections import defaultdict


N = int(input())
dict = defaultdict(int)


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)
    for ai in a:
        dict[ai] += 1


for i in range(1, N + 1):  
    prime_factorize(i)

ans = 0


for k1, v1 in dict.items():
    for k2, v2 in dict.items():
        for k3, v3 in dict.items():
            if k1 < k2 < k3:
                if v1 >= 2 and v2 >= 4 and v3 >= 4:
                    ans += 1
                if v1 >= 4 and v2 >= 2 and v3 >= 4:
                    ans += 1
                if v1 >= 4 and v2 >= 4 and v3 >= 2:
                    ans += 1

for k1, v1 in dict.items():
    for k2, v2 in dict.items():
        if k1 < k2:
            
            if v1 >= 14 and v2 >= 4:
                ans += 1
            if v1 >= 4 and v2 >= 14:
                ans += 1
            
            if v1 >= 24 and v2 >= 2:
                ans += 1
            if v1 >= 2 and v2 >= 24:
                ans += 1


for k1, v1 in dict.items():
    if v1 >= 74:
        ans += 1

print(ans)

Solution (Python):
from collections import defaultdict


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)
    for ai in a:
        dict[ai] += 1


N = int(input())
dict = defaultdict(int)


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)
    for ai in a:
        dict[ai] += 1


for i in range(1, N + 1):
    prime_factorize(i)

ans = 0


for k1, v1 in dict.items():
    for k2, v2 in dict.items():
        for k3, v3 in dict.items():
            if k1 < k2 < k3:
                if v1 >= 2 and v2 >= 4 and v3 >= 4:
                    ans += 1
                if v1 >= 4 and v2 >= 2 and v3 >= 4:
                    ans += 1
                if v1 >= 4 and v2 >= 4 and v3 >= 2:
                    ans += 1



for k1, v1 in dict.items():
    for k2, v2 in dict.items():
        if k1 < k2:
            if v1 >= 14 and v2 >= 4:
                ans += 1
            if v1 >= 4 and v2 >= 14:
                ans += 1
            if v1 >= 24 and v2 >= 2:
                ans += 1
            if v1 >= 2 and v2 >= 24:
                ans += 1


for k1, v1 in dict.items():
    if v1 >= 74:
        ans += 1

print(ans)

Solution (Python):
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def main():
	n = int(input())
	
	
	if n <= 9:
		return 0
	
	counter = collections.defaultdict(lambda :0)
	for i in range(2,n+1):
		v=i
		for ww in range(2,100):
			if v < ww:
				break
			while v%ww==0:
				counter[ww]+=1
				v=v//ww
				
	
	
	
	ret = 0
	
	for k in counter:
		if counter[k] >= 74:
			ret += 1
	
	
	n24 = 0
	n2 = 0
	for k in counter:
		if counter[k] >= 24:
			n24 += 1
		elif counter[k] >= 2:
			n2 += 1
	ret += (n24 * (n24-1))
	ret += n24 * n2
		
	
	n14 = 0
	n4 = 0
	for k in counter:
		if counter[k] >= 14:
			n14 += 1
		elif counter[k] >= 4:
			n4 += 1
	ret += (n14 * (n14-1))
	ret += n14 * n4
	
	
	n4 = 0
	n2 = 0
	for k in counter:
		if counter[k] >= 4:
			n4 += 1
		elif counter[k] >= 2:
			n2 += 1
	ret += (n4 * (n4-1) * (n4 - 2)) // 2
	ret += ((n4 * (n4-1)) // 2 ) * n2
	
	return ret
	
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
from collections import*
def cont(n):
  res=0
  n-=1
  for i in c:
    if i>=n:res+=1
  return res
def fact_p(n):
  m=n
  i=2
  a=[]
  while n>1:
    if i>m**.5:
      a+=[n]
      break
    if n%i==0:
      n//=i
      a+=[i]
    else:i+=1  
  return a
n=int(input())
a=[]
for i in range(1,n+1):
  a+=fact_p(i)
c=list(Counter(a).values())
print(cont(75)+cont(25)*(cont(3)-1)+cont(15)*(cont(5)-1)+cont(5)*(cont(5)-1)*(cont(3)-2)//2)

Solution (Python):
N=int(input())

def primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n+1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

x=primes(N//2+1)
s=[0]*len(x)

for n,i in enumerate(x):
    for j in range(1,7):
        if i**j > N:
            break
        s[n]+=N//(i**j)

c2=0
c4=0
c14=0
c24=0
c74=0
for i in s:
    if i>=2:
        c2+=1
        if i>=4:
            c4+=1
            if i>=14:
                c14+=1
                if i>=24:
                    c24+=1
                    if i>=74:
                        c74+=1
    else:
        break

ans=c4*(c4-1)//2*(c2-2)
ans+=c14*(c4-1)
ans+=c24*(c2-1)
ans+=c74
print(ans)

Solution (Python):
sosuu=[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]
N=int(input())
L=[0 for i in range(25)]
for i in range(25):
  s=N
  while True:
    if s!=0:
      s=s//sosuu[i]
      L[i]+=s
    else:
      break

a,b,c,d,e=0,0,0,0,0
for i in range(25):
  if L[i]>=74:
    a+=1
  if L[i]>=24:
    b+=1
  if L[i]>=14:
    c+=1
  if L[i]>=4:
    d+=1
  if L[i]>=2:
    e+=1
print(a+b*(e-1)+c*(d-1)+d*(d-1)*(e-2)//2)

Solution (Python):
class PrimeFactor():

    def __init__(self, n):
        """
        エラトステネス　O(N loglog N)
        """
        self.n = n
        self.table = list(range(n+1))       
        self.table[2::2] = [2]*(n//2)
        for p in range(3, int(n**0.5) + 2, 2):
            if self.table[p] == p:
                for q in range(p * p, n + 1, 2 * p):
                    if self.table[q] == q:
                        self.table[q] = p

    def is_prime(self, x):
        """ 素数判定　O(1) """
        if x < 2:
            return False
        return self.table[x] == x

    def prime_factors(self, x):
        """ 素因数分解 O(logN)  (試し割りだとO(sqrt(N))) """
        res = []
        if x < 2:
            return res
        while self.table[x] != 1:
            res.append(self.table[x])
            x //= self.table[x]
        return res

    def prime_counter(self, x):
        """ 素因数分解（個数のリスト） O(logN) """
        res = dict()
        if x < 2:
            return res
        while self.table[x] != 1:
            res[self.table[x]] = res.get(self.table[x], 0) + 1
            x //= self.table[x]
        return res


N = int(input())
P = PrimeFactor(N)
Q = dict()
for i in range(1,N+1):
    for key, value in P.prime_counter(i).items():
        Q[key] = Q.get(key,0) + value
a, b, c, d, e = 0, 0, 0, 0, 0
for value in Q.values():
    if value >= 2: a += 1
    if value >= 4: b += 1
    if value >= 24: c += 1
    if value >= 14: d += 1
    if value >= 74: e += 1
print(b*(b-1)//2*(a-2) + c*(a-1) + d*(b-1) + e)

Solution (Python):
def calc(N,p):
  ans = 0
  i = p
  while N>=i:
    ans += N//i
    i *= p
  return ans

def sieve(n):
  is_prime = [True for _ in range(n+1)]
  is_prime[0] = False
  for i in range(2, n+1):
    if is_prime[i-1]:
      j = 2 * i
      while j <= n:
        is_prime[j-1] = False
        j += i
  table = [i for i in range(1, n+1) if is_prime[i-1]]
  return table
  
from itertools import groupby, accumulate, product, permutations, combinations
def check(value,lis):
  ans = 0
  n = len(lis)
  for perm in permutations(value,n):
    for i in range(n):
      if perm[i]<lis[i]:
        break
    else:
      ans += 1
  return ans

def solve():
  N = int(input())
  table = sieve(N)
  v = []
  for p in table:
    v.append(calc(N,p))
  v.sort(reverse=True)
  ans = 0
  ans += check(v,[74])
  ans += check(v,[24,2])
  ans += check(v,[14,4])
  ans += check(v,[4,4,2])//2
  return ans
print(solve())

Solution (Python):
from collections import Counter
from itertools import chain


def prime_set(N):
    """
    Nまでの素数のsetを返す
    """
    if N < 4:
        return ({}, {}, {2}, {2, 3})[N]
    Nsq = int(N ** 0.5 + 0.5) + 1
    primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
    for i in range(5, Nsq, 2):
        if i in primes:
            primes -= set(range(i * i, N + 1, i * 2))
    return primes


def prime_factorization(n):  
    res = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            res.append((i, cnt))
    if n > 1:
        res.append((n, 1))
    return res


N = int(input())
primes = {p: 0 for p in prime_set(100)}
for i in range(2, N + 1):
    pf = prime_factorization(i)
    for p, f in pf:
        primes[p] += f


n2 = n4 = n14 = n24 = n74 = 0
for v in primes.values():
    if v >= 74:
        n74 += 1
    if v >= 24:
        n24 += 1
    if v >= 14:
        n14 += 1
    if v >= 4:
        n4 += 1
    if v >= 2:
        n2 += 1

ans = 0
if n74:
    ans += n74
if n24:
    ans += n24 * (n2 - 1)
if n14:
    ans += n14 * (n4 - 1)
if n4 >= 2 and n2:
    ans += n4 * (n4 - 1) // 2 * (n2 - 2)

print(ans)

Solution (Python):
P = [1 for _ in range(100)]
P[0]=0
P[1]=0
for i in range(2,11):
    for j in range(i**2,100,i):
        P[j] = 0
Q = []
for i in range(100):
    if P[i]==1:
        Q.append(i)
N = int(input())
C = {p:0 for p in Q}
for i in range(2,N+1):
    for p in Q:
        if i%p==0:
            x = i
            while x%p==0:
                x = x//p
                C[p] += 1
cnt = 0
for p in Q:
    if C[p]>=74:
        cnt += 1
cnt1 = 0
cnt2 = 0
for p in Q:
    if C[p]>=24:
        cnt2 += 1
    elif C[p]>=2:
        cnt1 += 1
cnt += cnt2*(cnt2-1)+cnt2*cnt1
cnt1 = 0
cnt2 = 0
for p in Q:
    if C[p]>=14:
        cnt2 += 1
    elif C[p]>=4:
        cnt1 += 1
cnt += cnt2*(cnt2-1)+cnt2*cnt1
cnt1 = 0
cnt2 = 0
for p in Q:
    if C[p]>=4:
        cnt2 += 1
    elif C[p]>=2:
        cnt1 += 1
cnt += (cnt2*(cnt2-1)*(cnt2-2))//2+((cnt2*(cnt2-1))//2)*cnt1
print(cnt)

Solution (Python):





n = int(input())

div = [0] * (n + 1)
for i in range(2, n + 1):
    j = 2
    while j * j <= i:
        while i % j == 0:
            div[j] += 1
            i //= j
        j += 1
    if i != 1:
        div[i] += 1

i3 = i5 = i15 = i25 = i75 = 0
for _, v in enumerate(div):
    if v >= 74:
        i75 += 1
    if v >= 24:
        i25 += 1
    if v >= 14:
        i15 += 1
    if v >= 4:
        i5 += 1
    if v >= 2:
        i3 += 1
ans = i75
ans += i25 * (i3 - 1)
ans += i15 * (i5 - 1)
ans += (i5 - 1) * i5 // 2 * (i3 - 2)
print(ans)

Solution (Python):
from collections import Counter
from itertools import combinations, permutations


def factor(n):
    res = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            res.append(i)
            n //= i
    if n > 1:
        return res + [n]
    else:
        return res


N = int(input())
if N < 10:
    print(0)
    exit()

cnt = Counter()
for i in range(2, N + 1):
    primes = factor(i)
    cnt += Counter(primes)

ans = 0
for x, y in combinations(cnt, 2):
    if cnt[x] < 4 or cnt[y] < 4:
        continue
    for z in cnt:
        if z == x or z == y or cnt[z] < 2:
            continue
        ans += 1

for x, y in permutations(cnt, 2):
    if cnt[x] >= 14 and cnt[y] >= 4:
        ans += 1

for x, y in permutations(cnt, 2):
    if cnt[x] >= 24 and cnt[y] >= 2:
        ans += 1

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

print(ans)

Solution (Python):
n = int(input())

import math
def factorize(n):
    d = {}
    temp = int(math.sqrt(n))+1
    for i in range(2, temp):
        while n%i== 0:
            n //= i
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
    if d == {}:
        d[n] = 1
    else:
        if n in d:
            d[n] += 1
        elif n != 1:
            d[n] =1
    return d

D = {}
for i in range(1, n+1):
    d = factorize(i)
    for k, v in d.items():
        if k in D:
            D[k] += v
        else:
            D[k] = v

p74 = 0
p24 = 0
p14 = 0
p4 = 0
p2 = 0
for k, v in D.items():
    if v >= 74:
        p74 += 1
        p24 += 1
        p14 += 1
        p4 +=1
        p2 +=1
    elif v >= 24:
        p24 += 1
        p14 += 1
        p4 +=1
        p2 +=1
    elif v >= 14:
        p14 += 1
        p4 +=1
        p2 +=1
    elif v >= 4:
        p4 +=1
        p2 +=1
    elif v >= 2:
        p2 +=1
    else:
        pass

ans = 0

ans += (p4*(p4-1)//2)*(p2-2)

ans += p24*(p2-1)

ans += p14*(p4-1)

ans += p74
print(ans)

Solution (Python):
N = int(input())

from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

fac = Counter()
for n in range(1,N+1):
    fac += factorize(n)

ans = 0
v4 = v2 = 0
for v in fac.values():
    if v >= 4:
        v4 += 1
    elif v >= 2:
        v2 += 1
t = v4 * (v4-1)//2 * (v4-2+v2)
if t > 0:
    ans += t

v24 = v2 = 0
for v in fac.values():
    if v >= 24:
        v24 += 1
    elif v >= 2:
        v2 += 1
t = v24 * (v24-1+v2)
ans += t

v14 = v4 = 0
for v in fac.values():
    if v >= 14:
        v14 += 1
    elif v >= 4:
        v4 += 1
t = v14 * (v14-1+v4)
ans += t

v74 = 0
for v in fac.values():
    if v >= 74:
        v74 += 1
ans += v74

print(ans)

Solution (Python):
def p_factorization(n):
    if n == 1: return {}
    pf_cnt = {}
    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
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    return pf_cnt


n = int(input())
pd = {}
for i in range(1,n+1):
    curr_p = p_factorization(i)
    for p,cnt in curr_p.items():
        pd.setdefault(p,0)
        pd[p] += cnt

ans = 0

cnt3 = 0
cnt5 = 0
cnt15 = 0
cnt25 = 0
cnt75 = 0

for v in pd.values():
    if v >= 74: cnt75 += 1
    if v >= 24: cnt25 += 1
    if v >= 14: cnt15 += 1
    if v >= 4: cnt5 += 1
    if v >= 2: cnt3 += 1


ans += cnt75
ans += max(cnt15*(cnt5-1), 0)
ans += max(0,cnt25*(cnt3-1))
ans += max(0,(cnt3-2)*(cnt5)*(cnt5-1)//2)
print(ans)

Solution (Python):
import sys
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]
num3=0
num5=0
num15=0
num25=0
num75=0
n=int(input())
for i in primes:
  tmp=0
  j=1
  while n//pow(i,j)>0:
    tmp+=n//pow(i,j)
    j+=1
  if tmp>=2:
    num3+=1
  if tmp>=4:
    num5+=1
  if tmp>=14:
    num15+=1
  if tmp>=24:
    num25+=1
  if tmp>=74:
    num75+=1
print(num75+max(0,(num3-1)*num25)+max(0,((num3-2)*(num5-1)*num5)//2)+max(0,((num5-1)*num15)))

Solution (Python):
def prime_factorize(N,lis):
    a = []
    n = N
    while n % 2 == 0:
        lis[2] += 1
        n //= 2
    f = 3
    while f * f <= N:
        if n % f == 0:
            lis[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        lis[n] += 1

N = int(input())
lis = [0] * 101
for i in range(1,N+1):
    prime_factorize(i,lis)
d = [0] * 100
for i in lis:
    d[i] += 1
for i in reversed(range(len(d)-1)):
    d[i] += d[i+1]

print(d[74] + d[24] * (d[2]-1) + d[14] * (d[4]-1) + (d[4] * (d[4]-1) * (d[2]-2)) // 2)

Solution (Python):
def prime_factorize(N,lis):
    a = []
    n = N
    while n % 2 == 0:
        lis[2] += 1
        n //= 2
    f = 3
    while f * f <= N:
        if n % f == 0:
            lis[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        lis[n] += 1

N = int(input())
lis = [0] * 101
for i in range(1,N+1):
    prime_factorize(i,lis)

lis.sort()
ans = 0
for i in range(101):
    for j in range(i+1,101):
        for k in range(j+1,101):
            if lis[i] >= 2 and lis[j] >= 4:
                ans += 1
            if lis[i] >= 4:
                ans += 2
for i in range(101):
    for j in range(i+1,101):
        if lis[i] >= 4 and lis[j] >= 14:
            ans += 1
            if lis[i] >= 14:
                ans += 1
        if lis[i] >= 2 and lis[j] >= 24:
            ans += 1
            if lis[i] >= 24:
                ans += 1
for i in range(101):
    if lis[i] >= 74:
        ans += 1
print(ans)

Solution (Python):
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


n = int(input())
cnt = [0]*101
ans=0

for i in range(1,n+1):
  lst = factorization(i)
  for j in lst:
    cnt[j[0]]+=j[1]

a,b,c,d,e=0,0,0,0,0

for i in cnt:
  if 2<=i<=3:
    a+=1
  elif 4<=i<=13:
    b+=1
  elif 14<=i<=23:
    c+=1
  elif 24<=i<=73:
    d+=1
  elif 74<=i:
    e+=1


ans+=e
ans+=(d+e)*(a+b+c+d+e-1)
ans+=(c+d+e)*(b+c+d+e-1)
ans+=(b+c+d+e)*(b+c+d+e-1)*(a+b+c+d+e-2)//2


print(ans)

Solution (Python):
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

n=int(input())
alist=[0]*101
for i in range(2,n+1):
  for j in factorization(i):
    alist[j[0]]+=j[1]
if n==1:
  print(0)
else:
  ans=0
  for i in range(1,100):
    if alist[i]>=74:
      ans+=1
    if alist[i]>=24:
      for j in range(1,100):
        if i!=j and alist[j]>=2:
          ans+=1
    if alist[i]>=14:
      for j in range(1,100):
        if i!=j and alist[j]>=4:
          ans+=1
    if alist[i]>=2:
      for j in range(1,100):
        for k in range(j+1,100):
          if i!=j and  k!=i and alist[j]>=4 and alist[k]>=4:
            ans+=1
  print(ans)

Solution (Python):
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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


def main():
    N = int(readline())

    prime = Counter()
    for n in range(1, N + 1):
        prime.update(prime_factorize(n))

    C = [0] * 101
    for v in prime.values():
        C[v] += 1

    for i in range(99, -1, -1):
        C[i] += C[i + 1]

    ans = 0
    ans += (C[2] - 2) * (C[4] * (C[4] - 1) // 2)
    ans += (C[2] - 1) * C[24]
    ans += (C[4] - 1) * C[14]
    ans += C[74]

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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


def com(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    r = min(r, n - r)
    numer = denom = 1
    for i in range(n - r + 1, n + 1):
        numer = numer * i
    for i in range(1, r + 1):
        denom = denom * i
    return numer // denom


def main():
    N = int(readline())

    prime = Counter()
    for n in range(1, N + 1):
        prime.update(prime_factorize(n))

    C = [0] * 101
    for v in prime.values():
        C[v] += 1

    for i in range(99, -1, -1):
        C[i] += C[i + 1]

    ans = 0
    ans += (C[2] - 2) * com(C[4], 2)
    ans += (C[2] - 1) * C[24]
    ans += (C[4] - 1) * C[14]
    ans += C[74]

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

n = int(input())
d = defaultdict(int)

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

for i in range(1, n+1):
    for x in prime_factorize(i):
        d[x] += 1





e = defaultdict(int)

l = [2, 4, 14, 24, 74]


for k, v in d.items():
    for x in l:
        if v >= x:
            e[x] += 1



ans = 0

ans += e[74]
ans += e[24] * (e[2] - 1)
ans += e[14] * (e[4] - 1)
ans += (e[4] * (e[4]-1) // 2) * (e[2] - e[4]) + (e[4] * (e[4]-1) * (e[4]-2) // 2)

print(ans)

Solution (Python):
import sys
from collections import defaultdict

input = sys.stdin.readline


def calc_prime_factors(n, count=False):
    """Trial division"""
    factors = []
    
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    
    f = 3
    root_n = int(n ** 0.5) + 1
    while f <= root_n:
        if n % f == 0:
            factors.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        factors.append(n)
    return factors


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

    n_factor = defaultdict(int)
    for n in range(1, N + 1):
        factors = calc_prime_factors(n)
        for f in factors:
            n_factor[f] += 1

    n_factor = list(n_factor.values())
    n_factor.sort()
    ans = 0

    
    A, B = 0, 0
    for n in n_factor:
        if 2 <= n <= 3:
            A += 1
        elif 4 <= n:
            B += 1
    ans += A * B * (B - 1) // 2 + B * (B - 1) * (B - 2) // 6 * 3

    
    A, B = 0, 0
    for n in n_factor:
        if 2 <= n <= 23:
            A += 1
        elif 24 <= n:
            B += 1
    ans += A * B + B * (B - 1)

    
    A, B = 0, 0
    for n in n_factor:
        if 4 <= n <= 13:
            A += 1
        elif 14 <= n:
            B += 1
    ans += A * B + B * (B - 1)

    
    A = 0
    for n in n_factor:
        if 74 <= n:
            A += 1
    ans += A

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import defaultdict

input = sys.stdin.readline


def calc_prime_factors(n, count=False):
    """Trial division"""
    factors = []
    
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    
    f = 3
    root_n = int(n ** 0.5) + 1
    while f <= root_n:
        if n % f == 0:
            factors.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        factors.append(n)
    return factors


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

    n_factor = defaultdict(int)
    for n in range(1, N + 1):
        factors = calc_prime_factors(n)
        for f in factors:
            n_factor[f] += 1

    n_factor = list(n_factor.values())
    n_factor.sort()
    ans = 0

    
    A, B = 0, 0
    for n in n_factor:
        if 2 <= n <= 3:
            A += 1
        elif 4 <= n:
            B += 1
    ans += A * B * (B - 1) // 2 + B * (B - 1) * (B - 2) // 6 * 3

    
    A, B = 0, 0
    for n in n_factor:
        if 2 <= n <= 23:
            A += 1
        elif 24 <= n:
            B += 1
    ans += A * B + B * (B - 1)

    
    A, B = 0, 0
    for n in n_factor:
        if 4 <= n <= 13:
            A += 1
        elif 14 <= n:
            B += 1
    ans += A * B + B * (B - 1)

    
    A = 0
    for n in n_factor:
        if 74 <= n:
            A += 1
    ans += A

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
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)

Solution (Python):
from collections import defaultdict


def main():
    n = int(input())
    fact = defaultdict(int)
    for i in range(2, n + 1):
        j = i
        while j % 2 == 0:
            j //= 2
            fact[2] += 1
        k = 3
        while k * k <= j:
            if j % k:
                k += 2
            else:
                j //= k
                fact[k] += 1
        if j != 1:
            fact[j] += 1
    fact = list(fact.items())
    length = len(fact)
    ans = 0
    for i in range(length):
        if fact[i][1] >= 74:
            ans += 1
    product = set()
    for small_p, large_p in [[2, 24], [4, 14]]:
        for i in range(length):
            for j in range(length):
                if i == j:
                    continue
                now = pow(fact[i][0], large_p) * pow(fact[j][0], small_p)
                if fact[i][1] >= large_p and fact[j][1] >= small_p and now not in product:
                    ans += 1
                    product.add(now)
    for i in range(length):
        for j in range(length):
            for k in range(length):
                if i == j or j == k or i == k:
                    continue
                now = pow(fact[i][0], 4) * pow(fact[j][0], 4) * pow(fact[k][0], 2)
                if fact[i][1] >= 4 and fact[j][1] >= 4 and fact[k][1] >= 2 and now not in product:
                    ans += 1
                    product.add(now)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

def primesbelow(N):
    
    
    correction = N % 6 > 1
    N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
    sieve = [True] * (N // 3)
    sieve[0] = False
    for i in range(int(N ** .5) // 3 + 1):
        if sieve[i]:
            k = (3 * i + 1) | 1
            sieve[k*k // 3::2*k] = [False] * ((N//6 - (k*k)//6 - 1)//k + 1)
            sieve[(k*k + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1)
    return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]]

n=int(input())
primes=primesbelow(n+10)
factor={}

def val(n,d):
    ans=0
    t=d
    while(t<=n):
        ans+=(n//t)
        t*=d
    return ans
g2=0
g4=0
g24=0
g14=0
g74=0
for i in primes:
    k=val(n,i)
    if k>=4:
        g4+=1
    if k>=2:
        g2+=1
    if k>=24:
        g24+=1
    if k>=14:
        g14+=1
    if k>=74:
        g74+=1

a=(g2-2)*((g4*(g4-1))//2)
b=g24*(g2-1)
c=g14*(g4-1)
d=g74
print(a+b+c+d)

Solution (Python):
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]
S = [0]*25

N = int(input())
for i in range(2, N+1):
    num = i
    j = 0
    while num > 1:
        if num%P[j] == 0:
            num //= P[j]
            S[j] += 1
        else:
            j += 1
            if j == 25:
                break






ans = 0
if S[0] >= 74:
    ans += 1
for i in range(3):
    if S[i] >= 24:
        tmp = -1
        for num in S:
            if num >= 2:
                tmp += 1
        ans += tmp
for i in range(4):
    if S[i] >= 14:
        tmp = -1
        for num in S:
            if num >= 4:
                tmp += 1
        ans += tmp
tmp4 = 0
tmp2 = 0
for num in S:
    if num >= 4:
        tmp4 += 1
    if num >= 2 and num < 4:
        tmp2 += 1
ans += tmp4*(tmp4-1)*(tmp4+tmp2-2)//2
print(ans)

Solution (Python):
"""
75数の条件
約数の個数は各素因数の個数a1,a2,a3,...について
(a1+1)(a2+1)...(an+1)
75=3*5*5
->素因数の個数が2個, 4個, 4個になるような組み合わせ
(2,4,4)
(14,4)
(2,24)
(74)

求め方
1〜Nについて、素因数の数をdictに収めていく
->そのうち、4個以上あるものの組み合わせと2個以上あるものの組み合わせでカウントする
"""
import copy
N=int(input())
sosu=[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]
soinsu=dict()
for n in range(2,N+1):
  if n in sosu:
    soinsu[n]=1
  else:
    x = copy.deepcopy(n)
    i = 0
    while i<len(sosu):
      if x % sosu[i]==0:
        soinsu[sosu[i]]+=1
        x = x//sosu[i]
      else:
        i += 1

ans = 0
cnt=[0,0,0,0,0]
tit=[2,4,14,24,74]
for _,v in soinsu.items():
  for i in range(5):
    cnt[i] += 1 if v >= tit[i] else 0


ans+= cnt[1]*(cnt[1]-1)//2*(cnt[0]-2)

ans+= cnt[2]*(cnt[1]-1)

ans+= cnt[3]*(cnt[0]-1)

ans+= cnt[4]
print(ans)

Solution (Python):
import sys
import math
import collections
import bisect
import copy



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    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 = ni()
    divisor = [0 for _ in range(101)]

    ans = 0
    for i in range(1, n + 1):
        a = prime_factorize(i)
        for ai in a:
            divisor[ai] += 1

    over75 = 0
    over25 = 0
    over15 = 0
    over5 = 0
    over3 = 0
    for di in divisor:
        tmp = di + 1
        if tmp >= 75:
            over75 += 1
        if tmp >= 25:
            over25 += 1
        if tmp >= 15:
            over15 += 1
        if tmp >= 5:
            over5 += 1
        if tmp >= 3:
            over3 += 1

    ans = over75 + over25 * (over3 - 1) + over15 * (over5 - 1) + over5 * (over5 - 1) // 2 * (over3 - 2)

    print(ans)


if __name__ == '__main__':
    main()