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 Counter
from math import factorial

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

def prime_factoring(n):
    from collections import Counter
    a = prime_factorize(n)
    return Counter(a)

N = int(input())
fac =factorial(N)
List = prime_factoring(fac).values()


def num(m):
    return len(list(filter(lambda x: x >= m-1, List)))
print(num(75)+ num(25)*(num(3)-1) + num(15)*(num(5)-1)+ num(5)*(num(5)-1)*(num(3)- 2)//2)

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




from collections import defaultdict
memo=defaultdict(lambda:-1)

def f(x):
    if memo[x]!=-1:return memo[x]
    ret=0;temp=n
    while temp:
        temp//=x
        ret+=temp
    memo[x]=ret
    return ret
ans=0
primes=[2,3]
for i in range(5,101,6):
    for p in primes:
        if i%p:continue
        break
    else:primes.append(i)
    i+=2
    for p in primes:
        if i%p:continue
        break
    else:primes.append(i)
di=[i**2 for i in primes]
qu=[j**2 for j in di]
for p in primes:
    if f(p)>=74:ans+=1
    else:break
def g(a,b):
    global ans
    for p in primes:
        if f(p)>=a:
            for q in primes:
                if f(q)>=b:
                    if q!=p:ans+=1
                    else:continue
        else:break
    return 0
g(2,24)
g(4,14)

for q in range(len(qu)):
    for r in range(q+1,len(qu)):
        a,b=qu[q],qu[r]
        if not (f(primes[q])>=4 and f(primes[r])>=4):continue
        for i,d in enumerate(di):
            if d**2 not in {a,b} and f(primes[i])>=2:ans+=1
print(ans)

Solution (Python):
from collections import Counter
from math import factorial

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

def prime_factoring(n):
    from collections import Counter
    a = prime_factorize(n)
    return Counter(a)

N = int(input())
fac =factorial(N)
List = prime_factoring(fac).values()


def num(m):
    return len(list(filter(lambda x: x >= m-1, List)))
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 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

def main():
    N = int(input())
    d = defaultdict(int)
    for i in range(1,N+1):
        for j in prime_factor(i):
            d[j] += 1
    
    
    
    
    e = defaultdict(int)
    for i, j in d.items():
        if j >= 2:
            e[2] += 1
        if j >= 4:
            e[4] += 1
        if j >= 14:
            e[14] += 1
        if j >= 24:
            e[24] += 1
        if j >= 74:
            e[74] += 1
    ans = 0
    ans += (e[2] - 1) * e[24]
    ans += (e[4] - 1) * e[14]
    ans += e[74]
    ans += (e[2] - 2) * e[4] * (e[4] - 1) // 2
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter
N = int(input())

l = []
for i in range(1, N+1):
  while i % 2 == 0:
    l.append(2)
    i //= 2
  f = 3
  while f * f <= i:
    if i % f == 0:
      l.append(f)
      i //= f
    else:
      f += 2
  if i != 1:
    l.append(i)

c = Counter(l)
m = c.most_common()
c_75, c_25, c_15, c_5, c_3 = 0, 0, 0, 0, 0
for a in m:
  if a[1] >= 74:
    c_75 += 1
  if a[1] >= 24:
    c_25 += 1
  if a[1] >= 14:
    c_15 += 1
  if a[1] >= 4:
    c_5 += 1
  if a[1] >= 2:
    c_3 += 1
    
ans = c_75
ans += c_25 * (c_3-1)
ans += c_15 * (c_5-1)
ans += (c_5*(c_5-1)//2) * (c_3-2)
print(ans)

Solution (Python):
import math
n=int(input())
p=[0]*101
dp=[0]*101
for i in range(2,n+1):
  for j in range(2,i+1):
    while i%j==0:
      i//=j
      p[j]+=1
for i in range(101):
  if p[i]!=0:
    dp[p[i]]+=1
ans=sum(dp[74:])+sum(dp[24:])*(sum(dp[2:])-1)+sum(dp[14:])*(sum(dp[4:])-1)+sum(dp[4:])*(sum(dp[4:])-1)//2*(sum(dp[2:])-2)
print(ans)

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):





def prime_factorization(x):
    """素因数分解"""
    import math
    re = []
    i = 2
    while x != 1:
        if x % i == 0:
            re.append(i)
            x //= i
        else:
            i += 1
            if i > math.sqrt(x):
                re.append(x)
                break
    return re






def solve(N):
    pf = []
    for i in range(1, N + 1):
        pf += prime_factorization(i)
    pf_nums = [0] * (N + 1)
    for p in pf:
        pf_nums[p] += 1

    def num(m):
        return len([i for i in pf_nums 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)


if __name__ == '__main__':
    N = int(input())
    solve(N)

Solution (Python):





def prime_factorization(x):
    """素因数分解"""
    import math
    re = []
    i = 2
    while x != 1:
        if x % i == 0:
            re.append(i)
            x //= i
        else:
            i += 1
            if i > math.sqrt(x):
                re.append(x)
                break
    return re


def cmb(n, r):
    """組み合わせ"""
    import math
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))






def solve(N):
    pf = []
    for i in range(1, N + 1):
        pf += prime_factorization(i)
    pf_num = {}
    for p in pf:
        pf_num.setdefault(p, 0)
        pf_num[p] += 1
    over2 = 0
    over4 = 0
    over14 = 0
    over24 = 0
    over74 = 0
    for v in pf_num.values():
        if 74 <= v:
            over74 += 1
        if 24 <= v:
            over24 += 1
        if 14 <= v:
            over14 += 1
        if 4 <= v:
            over4 += 1
        if 2 <= v:
            over2 += 1
    ans = 0
    
    ans += (over2 - over4) * cmb(over4, 2)
    ans += cmb(over4, 3) * 3

    
    ans += (over4 - over14) * over14
    ans += cmb(over14, 2) * 2

    
    ans += (over2 - over24) * over24
    ans += cmb(over24, 2) * 2

    
    ans += over74

    print(ans)


if __name__ == '__main__':
    N = int(input())
    solve(N)

Solution (Python):
import itertools

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

a=[]
for i in range(2,n+1):
    aa=prime_decomposition(i)
    a.extend(aa)
    
a.sort()

i75=0
i25=0
i15=0
i5=0
i3=0
gr = itertools.groupby(a)
for key, group in gr:
    ll=len(list(group))

    if ll>=74:
        i75+=1
    if ll>=24:
        i25+=1
    if ll>=14:
        i15+=1
    if ll>=4:
        i5+=1
    if ll>=2:
        i3+=1
ans=0
ans=ans+i75
ans=ans+i25*max(i3-1,0)
ans=ans+i15*max(i5-1,0)
ans=ans+i5*max(i5-1,0)*max(i3-2,0)//2
print(ans)

Solution (Python):


def factorize(n):
    '''
    タプルの配列と思ったけど逐次割り算する過程で次数を増やせないじゃん。
    二重配列?
    dictにしよう。
    '''
    if n == 1:
        raise('n >= 2')
    
    factor = {}
    div = 2
    while True:
        if n % div == 0:
            n //= div
            factor[div] = factor.get(div, 0) + 1
            if n == 1:
                return factor
        else:
            div += 1

n = int(input())

if n <= 9:
    print(0)
    exit()


import math
product = math.prod(range(1, n+1))
d = factorize(product)
factor = list(d.items())



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

for i in range(len(factor)):
    for j in range(len(factor)):
            if factor[i][1] >= 4 and factor[j][1] >= 14 and i!=j:
                ans += 1

for i in range(len(factor)):
    for j in range(len(factor)):
            if factor[i][1] >= 2 and factor[j][1] >= 24 and i!=j:
                ans += 1

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

print(ans)

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

n=int(input())
x=[0]*(n+1)
for i in range(1,n+1):
  for j in num_div(i):
    x[j]+=1
ex2=len([i for i in x if i>1])
ex4=len([i for i in x if i>3])
ex14=len([i for i in x if i>13])
ex24=len([i for i in x if i>23])
ex74=len([i for i in x if i>73])
print(ex4*(ex4-1)//2*(ex2-2)+ex24*(ex2-1)+ex14*(ex4-1)+ex74)

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

fact_ct = [0 for _ in range(N+1)]
pr = []

def primes():
  ans = set()
  visited = set()
  for p in range(2,N+1):
    if p in visited:
      continue
    ans.add(p)
    q = p
    while q <= N:
      visited.add(q)
      q += p    
  return ans

pr = primes() 

def add_fact_ct(n):
  visited = set()
  for p in range(2,N+1):
    if p not in pr:
      continue
    while n % p == 0:
      fact_ct[p] += 1
      n //= p  

for n in range(2, N+1):
  add_fact_ct(n)
  
ct_75 = 0
ct_25 = 0
ct_15 = 0
ct_5 = 0
ct_3 = 0
ct_1 = 0
  
for ct in fact_ct:
  if ct >= 74:
    ct_75 += 1
  if ct >= 24:
    ct_25 += 1
  if ct >= 14:
    ct_15 += 1
  if ct >= 4:
    ct_5 += 1 
  if ct >= 2:
    ct_3 += 1

ans = 0

ans += ct_75

ans += ct_25 * (ct_3-1)
ans += ct_15 * (ct_5-1)

ans += ct_5*(ct_5-1)*(ct_3-2) // 2

print(ans)

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("YES") if fl else print("NO")
import collections
import math
import itertools
import heapq as hq
import sys

n = ni()
def factorize(n):
    b = 2
    fct = [(1,1)]
    while b * b <= n:
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        b = b + 1
    if n > 1:
        fct.append((n,1))
    return fct

co = collections.Counter()
for i in range(2,n+1):
    fct = factorize(i)
    for num,cnt in fct:
        if num>1:
            co[num]+=cnt
f4 = 0
f2 = 0
f14 = 0
f24=0
f74=0
for cnt in co.values():
    if cnt>=74:
        f74+=1
    if cnt>=24:
        f24+=1
    if cnt>=14:
        f14+=1
    if cnt>=4:
        f4+=1
    if cnt>=2:
        f2+=1



ans = f74 + f24*(f2-1) +f14*(f4-1)+f4*(f4-1)//2*(f2-2)

print(ans)

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

if n < 10:
    print(0)
    exit()

prime = [2, 3]
for i in range(5, n+1, 2):
    for p in prime:
        if i % p == 0:
            break
    else:
        prime.append(i)


num = []
for p in prime:
    cnt = 1
    now = p
    while now <= n:
        cnt += n // now
        now *= p
    num.append(cnt)

more3 = [i for i in num if i >= 3]
more5 = [i for i in more3 if i >= 5]
more15 = [i for i in more5 if i >= 15]
more25 = [i for i in more15 if i >= 25]
more75 = [i for i in more25 if i >= 75]

more3 = len(more3); more5 = len(more5); more15 = len(more15); more25 = len(more25); more75 = len(more75)

print(more25 * (more3 - 1) + more15 * (more5 - 1) + more5 * (more5 - 1) * (more3 - 2) // 2 + more75)

Solution (Python):
import sys
import math
import itertools



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


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)

    if temp != 1:
        arr.append(temp)

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


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

    P = [0] * (N + 1)

    for i in range(1, N + 1):
        arr = factorization(i)
        for s in arr:
            P[s] += 1

    ans = 0
    PN = []
    for j in P:
        if j != 0:
            PN.append(j)

    ans = 0
    count = 0
    
    for i in PN:
        if i >= 74:
            count += 1
    ans += count

    count = 0
    
    sub1 = 0
    sub2 = 0
    for i in PN:

        if i >= 24:
            sub1 += 1
        if i >= 2:
            sub2 += 1
    ans += sub1 * (sub2 - 1)

    
    sub1 = 0
    sub2 = 0
    for i in PN:

        if i >= 14:
            sub1 += 1
        if i >= 4:
            sub2 += 1
    ans += sub1 * (sub2 - 1)

    
    sub1 = 0
    sub2 = 0
    for i in PN:

        if i >= 4:
            sub1 += 1
        if i >= 2:
            sub2 += 1
    ans += sub1 * (sub1 - 1)*(sub2-2)//2


    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict


def factorize(N):  
    p = 2 
    while p * p <= N:
        while N % p == 0:
            N //= p
            fact[p] += 1
        p += 1
    if N > 1:
        fact[N] += 1

n = int(input())

fact = defaultdict(int)
for i in range(n):
    factorize(i + 1)

cnt = {2: 0, 4: 0, 14: 0, 24: 0, 74: 0}
for vfact in fact.values():
    for i in cnt:
        cnt[i] += (vfact >= i)

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

Solution (Python):
from collections import defaultdict


def factorize(N):  
    p = 2 
    while p * p <= N:
        while N % p == 0:
            N //= p
            fact[p] += 1
        p += 1
    if N > 1:
        fact[N] += 1

n = int(input())
fact = defaultdict(int)
for i in range(n):
    factorize(i + 1)

cnt4 = sum(cnt >= 4 for cnt in fact.values())
cnt2 = sum(cnt >= 2 for cnt in fact.values())
cnt24 = sum(cnt >= 24 for cnt in fact.values())
cnt14 = sum(cnt >= 14 for cnt in fact.values())
cnt74 = sum(cnt >= 74 for cnt in fact.values())

ans = cnt4 * (cnt4 - 1) * (cnt2 - 2) // 2
ans += cnt24 * (cnt2 - 1) + (cnt4 - 1) * cnt14 + cnt74
print(ans)

Solution (Python):


import sys 
import math
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())

def prime_factorize(n,cnt):
    for i in range(2,int(math.sqrt(n))+1):
        if n % i == 0:
            while n % i ==0:
                n //= i
                cnt[i] +=1
    if n != 1:
        cnt[n] +=1
    return 

cnt = defaultdict(int)
for i in range(2,N+1):
    prime_factorize(i,cnt)

def num(n):
    c = 0
    for v in cnt.values():
        if v < n:
            break
        c += 1
    return c 

print(num(74) + num(24)*(num(2)-1) + num(14)*(num(4)-1) + num(4)*(num(4)-1)*(num(2)-2)//2)

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

prime_1 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
prime_2 = [4,9,25,49]
prime_3 = [8,27]
prime_4 = [16,81]

dp = [0]*15

for i in range(15):
    dp[i] += n // prime_1[i]

for j in range(4):
    dp[j] += n // prime_2[j]
    
for k in range(2):
    dp[k] += n // prime_3[k]

for l in range(2):
    dp[l] += n // prime_4[l]

dp[0] += n // 32
dp[0] += n // 64

n2 = sum(x>1 for x in dp) 
n4 =sum(x>3 for x in dp)
n14=sum(x>13 for x in dp)
n24=sum(x>23 for x in dp)
n74=sum(x>73 for x in dp)

p553 = (n2-n4) * (n4*(n4-1) //2 ) + ((n4*(n4-1)*(n4-2))//2)
p144 = (n4-n14) * n14 + (n14*(n14-1))
p242 = (n2-n24) * n24 + (n24*(n24-1))
p750 = n74

print(p553+p144+p242+p750)

Solution (Python):


n = int(input())


is_prime = [True for _ in range(100)]
is_prime[0] = is_prime[1] = False
for i in range(100):
    if not is_prime[i]:continue 
    for j in range(i*i, 100, i): 
        if not is_prime[j]: 
            is_prime[j] = False

factor = [0 for _ in range(100)]
for i in range(2, n+1):
    for j in range(2, 100):
        if is_prime[j]:
            while i%j == 0:
                factor[j] += 1
                i //= j




fs = []
for i in range(100):
    if factor[i] != 0:
        fs.append(factor[i])



m = len(fs)
ans = [0 for _ in range(4)]
for i in range(m):
    for j in range(m):
        for k in range(m):
            if i!=j and j!=k and k!=i:
                if fs[i] >= 4 and fs[j] >= 4 and fs[k] >=2:
                    ans[0] += 1

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

for i in range(m):
    for j in range(m):
        if i!=j:
            if fs[i] >= 2 and fs[j] >= 24: 
                ans[2] += 1

for i in range(m):
    for j in range(m):
        if i!=j:
            if fs[i] >= 4 and fs[j] >= 14: 
                ans[3] += 1


Ans = ans[0]//2 + ans[1] + ans[2] + ans[3]
print(Ans)

Solution (Python):

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())

d = {}
for i in range(2, n+1):
    p = prime_factorize(i)
    for cp in p:
        if cp in d:
            d[cp] += 1
        else:
            d[cp] = 1

cnt = {75:0, 25:0, 15:0, 5:0, 3:0}
for i in d:
    for j in cnt:
        if d[i] >= j-1:
            cnt[j] += 1
ans = cnt[75] + cnt[25]*(cnt[3]-1) + cnt[15]*(cnt[5]-1) + cnt[5]*(cnt[5]-1)//2*(cnt[3]-2)
print(ans)

Solution (Python):
N = int(input())
c = (N+1)*[0]

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

f = lambda x:sum(y+1>=x for y in c)
print(f(75)+f(25)*(f(3)-1)+f(15)*(f(5)-1)+f(5)*(f(5)-1)//2*(f(3)-2))

Solution (Python):
from collections import defaultdict
N=int(input())
fac = defaultdict(int)

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])
            fac[i] += cnt

    if temp!=1:
        arr.append([temp, 1])
        fac[temp] += 1 

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

for num in range(2, N+1):
    factorization(num)

ans = 0

num_74 = set()
num_24 = set()
num_14 = set()
num_4 = set()
num_2 = set()
for key, value in fac.items():
    if value >= 74:
        num_74.add(key)
    if value >= 24:
        num_24.add(key)
    if value >= 14:
        num_14.add(key)
    if value >= 4:
        num_4.add(key)
    if value >= 2:
        num_2.add(key)

ans += len(num_74)


ans += len(num_24) * (len(num_2)-1)




ans += len(num_14) * (len(num_4) - 1)



ans += len(num_2.difference(num_4)) * len(num_4)*(len(num_4)-1)//2 + len(num_4) * (len(num_4)-1)*(len(num_4)-2)//2


print(ans)

Solution (Python):
from collections import Counter

count = Counter([])

N = int(input())

for i in range(2,N+1):
    n = i
    tmp = []
    d = 2
    while d <= n:
        while n%d == 0:
            n //= d
            tmp.append(d)
        d += 1
    count += Counter(tmp)

ans = 0

for v in count.values():
    if v >= 74:
        ans += 1


more24 = 0
more2 = 0
for v in count.values():
    if v >= 2:
        more2 += 1
    if v >= 24:
        more24 += 1

ans += more24*(more2-more24)
ans += more24*(more24-1)


more14 = 0
more4 = 0
for v in count.values():
    if v >= 4:
        more4 += 1
    if v >= 14:
        more14 += 1
ans += more14 * (more4-more14)
ans += more14*(more14-1)


ans += more4*(more4-1)//2 * (more2-more4)
ans += more4*(more4-1)//2*(more4-2)

print(ans)

Solution (Python):
from collections import defaultdict
primes = list(range(2,101))
for i in range(len(primes)):
    if primes[i]:
        j = i
        j += primes[i]
        while j < len(primes):
            primes[j] = None
            j += primes[i]
primes = [p for p in primes if p]
N = int(input())
fact = defaultdict(int)
for p in primes:
    i = p
    while i <= N:
        fact[p] += N//i
        i *= p
f2 = set()
f4 = set()
f14 = set()
f24 = set()
f74 = set()
for p in fact:
    if fact[p] >= 2:
        f2.add(p)
    if fact[p] >= 4:
        f4.add(p)
    if fact[p] >= 14:
        f14.add(p)
    if fact[p] >= 24:
        f24.add(p)
    if fact[p] >= 74:
        f74.add(p)
ans = 0
ans += len(f74)
ans += len(f24)*(len(f2)-1)
ans += len(f14)*(len(f4)-1)
ans += (len(f2)-2)*len(f4)*(len(f4)-1)//2
print(ans)

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

prime_factor = {1: 1} if n == 1 else {}
for i in range(2, n+1):
    while i % 2 == 0:
        prime_factor[2] = prime_factor.get(2, 0) + 1
        i //= 2
    f = 3
    while f * f <= i:
        if i % f == 0:
            prime_factor[f] = prime_factor.get(f, 0) + 1
            i //= f
        else:
            f += 2
    if i != 1:
        prime_factor[i] = prime_factor.get(i, 0) + 1

m = len(prime_factor)
prime = list(prime_factor.keys())

dp = [[0]*76 for _ in range(m+2)]
dp[0][1] = 1
for i in range(m):
    for j in range(76):
        for k in range(prime_factor[prime[i]]+1):
            if (v := j * (k+1)) < 76:
                dp[i+1][v] += dp[i][j]

print(dp[m][75])

Solution (Python):
n=int(input())
w=[0 for i in range(101)]
for m in range(2,n+1):
    tmp=m
    for j in range(2,m+1):
        while tmp%j==0:
            w[j]+=1
            tmp//=j
def num(a):
    return len(list(filter(lambda x:x>=a-1,w)))
print(num(75)+num(25)*(num(3)-1) + num(15) * (num(5) - 1)
+ num(5) * (num(5) - 1) * (num(3) - 2) // 2)

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


import math
def nCr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def factorization(n):
    '''
    [base,power]のリストを返す
    '''
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 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

base_power = [0] * 100
for i in range(2,n+1):
    arr = factorization(i)
    for base, power in arr:
        base_power[base] += power

More_2 = 0
More_4 = 0
More_14 = 0
More_24 = 0
More_74 = 0
for base in range(100):
    if base_power[base] >= 2:
        More_2 += 1
    if base_power[base] >= 4:
        More_4 += 1
    if base_power[base] >= 14:
        More_14 += 1
    if base_power[base] >= 24:
        More_24 += 1
    if base_power[base] >= 74:
        More_74 += 1

ans = 0
if More_2 - 2 > 0 and More_4 >= 2:
    ans += nCr(More_4,2)*(More_2-2)
if More_2 - 1 > 0 and More_24 > 0:
    ans += More_24 * (More_2-1)
if More_14 > 0 and More_4-1>0:
    ans += More_14 * (More_4-1)
if More_74 > 0:
    ans += More_74
print(ans)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def primeFactorization(n):
    ans = []
    temp = n
    while temp%2 == 0:
        ans.append(2)
        temp //= 2
    for i in range(3, int(n**0.5)+1, 2):
        while temp%i == 0:
            ans.append(i)
            temp //= i
    if temp > 1:
        ans.append(temp)
    return collections.Counter(ans)

def resolve():
    N = I()

    
    pf_N_fact = collections.Counter()
    for i in range(1, N + 1):
        pf = primeFactorization(i)
        for k, v in pf.items():
            pf_N_fact[k] += v
    l = list(pf_N_fact.values())
    l.sort()
    pf_num = len(pf_N_fact)

    
    
    
    ans = 0
    num_2 = pf_num - bisect.bisect_left(l, 2)
    num_4 = pf_num - bisect.bisect_left(l, 4)
    num_14 = pf_num - bisect.bisect_left(l, 14)
    num_24 = pf_num - bisect.bisect_left(l, 24)
    num_74 = pf_num - bisect.bisect_left(l, 74)
    ans += num_4 * (num_4 - 1) // 2 * (num_2 - 2)
    ans += num_24 * (num_2 - 1)
    ans += num_14 * (num_4 - 1)
    ans += num_74
    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def primeFactorization(n):
    ans = []
    temp = n
    while temp%2 == 0:
        ans.append(2)
        temp //= 2
    for i in range(3, int(n**0.5)+1, 2):
        while temp%i == 0:
            ans.append(i)
            temp //= i
    if temp > 1:
        ans.append(temp)
    return collections.Counter(ans)

def resolve():
    N = I()

    
    pf_N_fact = collections.Counter()
    for i in range(1, N + 1):
        pf = primeFactorization(i)
        for k, v in pf.items():
            pf_N_fact[k] += v
    l = list(pf_N_fact.values())
    l.sort()
    pf_num = len(pf_N_fact)

    
    
    
    ans = 0
    num_2 = pf_num - bisect.bisect_left(l, 2)
    num_4 = pf_num - bisect.bisect_left(l, 4)
    num_14 = pf_num - bisect.bisect_left(l, 14)
    num_24 = pf_num - bisect.bisect_left(l, 24)
    num_74 = pf_num - bisect.bisect_left(l, 74)
    ans += num_4 * (num_4 - 1) // 2 * max(num_2 - 2, 0)
    ans += num_24 * max(num_2 - 1, 0)
    ans += num_14 * max(num_4 - 1, 0)
    ans += num_74
    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
import collections

def fact(N):
    arr = []
    i=2
    while i*i<=N:
        if N%i==0:
            while N%i==0:
                arr.append(i)
                N//=i
        i+=1
    if N>1:
        arr.append(N)
    return arr

N=int(input())
arr = []
for i in range(1,N+1):
    arr += fact(i)

arc=collections.Counter(arr)
num74cnt=0
num24cnt=0
num14cnt=0
num4cnt=0
num2cnt=0
for val in arc.values():
    if val >=74:
        num74cnt+=1
    if val >=24:
        num24cnt+=1
    if val >=14:
        num14cnt+=1
    if val >= 4:
        num4cnt+=1
    if val >= 2:
        num2cnt +=1
ans = num74cnt
ans += num24cnt*(num2cnt-1)
ans += num14cnt*(num4cnt-1)
ans += num4cnt*(num4cnt-1)//2*(num2cnt-2)

print(ans)

Solution (Python):
from collections import *

def factorize(n):
    fct = []
    
    for i in range(2, int(n**0.5)+1):
        c = 0
        
        while n%i==0:
            n //= i
            c += 1
        
        if c>0:
            fct.append((i, c))

    if n!=1:
        fct.append((n, 1))
    
    return fct

N = int(input())
cnt = defaultdict(int)

for i in range(1, N+1):
    fct = factorize(i)
    
    for p, c in fct:
        cnt[p] += c

c2, c4, c14, c24, c74 = 0, 0, 0, 0, 0

for v in cnt.values():
    if v>=2:
        c2 += 1
        
    if v>=4:
        c4 += 1
        
    if v>=14:
        c14 += 1
        
    if v>=24:
        c24 += 1
        
    if v>=74:
        c74 += 1

print(c74+c4*max(0, c4-1)//2*max(0, c2-2)+c24*max(0, c2-1)+c14*max(0, c4-1))

Solution (Python):
"""
実際にN!を計算するわけには行かない。
memo[n] => nの素因数分解の結果

sum(memo[N])の素因数分解の結果から
"""
from collections import Counter
N = int(input())
memo = [None]*(N+1)

for i in range(2,N+1):
    tmp = []
    n = i
    d = 2
    while n!=1:
        while n%d==0:
            tmp.append(d)
            n//=d
        d += 1
    memo[i] = Counter(tmp)

count = Counter([])
for i in range(2,N+1):
    count += memo[i]

ans = 0

c74 = 0

c24 = 0

c14 = 0

c4 = 0

c2 = 0

for v in count.values():
    if v >= 2:
        c2 += 1
    if v >= 4:
        c4 += 1
    if v >= 14:
        c14 += 1
    if v >= 24:
        c24 += 1
    if v >= 74:
        c74 += 1

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


"""

for k,v in count.items():
    if v >= 74:
        ans += 1
    

for k,v in count.items():
    if v >= 24:
        for k2,v2 in count.items():
            if k2 != k and v2 >= 2:
                ans += 1


for k,v in count.items():
    if v >= 14:
        for k2,v2 in count.items():
            if k2 != k and v2 >= 4:
                ans += 1


for k,v in count.items():
    if v >= 4:
        for k2,v2 in count.items():
            if k2 != k and v2 >= 4:
                for k3,v3 in count.items():
                    if k3 != k and k3!=k2 and v3 >= 2:
                        ans += 1
"""

print(ans)

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)))


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

Solution (Python):
from collections import defaultdict
N = int(input())
prm = defaultdict(int)
for n in range(2, N+1):
    for p in range(2, int(n**0.5)+2):
        while n % p == 0:
            prm[p] += 1
            n //= p
        if n == 1:
            break
    else:
        prm[n] += 1
C = [2, 4, 14, 24, 74]
cnt = [0]*5
for p, x in prm.items():
    for i, c in enumerate(C):
        if x >= c:
            cnt[i] += 1
c2, c4, c14, c24, c74 = cnt

ans = c4*(c4-1)//2*(c2-2) if c2 > 2 else 0
ans += max(0, c24*(c2-1))
ans += max(0, c14*(c4-1))
ans += c74
print(ans)