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


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


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


def main():
    N = int(input())
    A = [0 for _ in range(N + 1)]
    for i in range(1, N + 1):
        F = factorization(i)
        for f in F:
            A[f[0]] += f[1]
    cnt = [0 for _ in range(5)]
    for a in A:
        if a >= 74:
            cnt[0] += 1
        elif a >= 24:
            cnt[1] += 1
        elif a >= 14:
            cnt[2] += 1
        elif a >= 4:
            cnt[3] += 1
        elif a >= 2:
            cnt[4] += 1
    answer = cnt[0]
    answer += sum(cnt[:2]) * sum(cnt[2:])
    answer += sum(cnt[:2]) * (sum(cnt[:2]) - 1)
    answer += sum(cnt[:3]) * (sum(cnt[3:-1]))
    answer += sum(cnt[:3]) * (sum(cnt[:3]) - 1)
    answer += sum(cnt[:4]) * (sum(cnt[:4]) - 1) * cnt[-1] // 2
    answer += sum(cnt[:4]) * (sum(cnt[:4]) - 1) * (sum(cnt[:4]) - 2) // 2
    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter

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

def fac(n):
    ans=1
    for i in range(n,0,-1):
        ans*=i
    return ans

n=int(input())
c = Counter(prime_factorize(fac(n)))
v=c.values()
cnt={74:0,24:0,14:0,4:0,2:0}
for i in v:
    if i>=74:
        cnt[74]+=1
    if i>=24:
        cnt[24]+=1
    if i>=14:
        cnt[14]+=1
    if i>=4:
        cnt[4]+=1
    if i>=2:
        cnt[2]+=1
ans=cnt[74]+cnt[24]*(cnt[2]-1)+cnt[14]*(cnt[4]-1)+cnt[4]*(cnt[4]-1)*(cnt[2]-2)//2
print(ans)

Solution (Python):
n = int(input())
import  numpy as np
fact = np.zeros(100)
def prime_factorize(n):
    while n % 2 == 0:
        fact[1]+=1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            fact[f-1] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        fact[n-1] += 1

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

def num(a):
  return sum(fact>=a-1)

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 inputlist(): return [int(k) for k in input().split()]


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())
if N == 1:
    print(0)
    exit()
dp = [[0]*101 for _ in range(N+1)]
for i in range(2,N+1):
    li = factorization(i)
    n = len(li)
    li0 = [0]*n
    li1 = {}
    for k in range(n):
        li0[k] = li[k][0]
        li1[li[k][0]] = li[k][1]
    for j in range(2,101):
        if j in li0:
            dp[i][j] = dp[i-1][j] + li1[j]
            continue
        dp[i][j] = dp[i-1][j]

li = dp[N]
li.sort()
from bisect import bisect_right
indexa = bisect_right(li,0)
lia = li[indexa:]

na = len(lia)
c2 = 0
c4 = 0
c14 = 0
c24 = 0
c74 = 0
for i in range(na):
    if lia[i] >= 2:
        c2+=1
    if lia[i] >= 4:
        c4+=1
    if lia[i] >= 14:
        c14 +=1
    if lia[i] >= 24:
        c24+=1
    if lia[i] >= 74:
        c74+=1
d4_2 = c2-c4
d14_4 = c4 - c14
d24_2 = c2 - c24

def comb2(i):
    return i*(i-1)//2
def comb3(i):
    return i*(i-1)*(i-2)//6

ans = d4_2*comb2(c4) + 3*comb3(c4) + d14_4*c14 + 2*comb2(c14) + d24_2*c24 + 2*comb2(c24) +c74
print(ans)

Solution (Python):
N=int(input())
numbers = {2: 0, 3: 0, 5: 0,7: 0, 11: 0, 13: 0, 17: 0, 19: 0, 23: 0, 29: 0, 31: 0, 37: 0, 41: 0, 43: 0, 47: 0, 53: 0, 59: 0, 61: 0, 67: 0, 71: 0, 73: 0, 79: 0, 83: 0, 89: 0, 97: 0}
prime = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97)
for n in range(2,N+1):
    a=n
    while(a!=1):
        for j in prime:
            if(a%j==0):
                numbers[j]+=1
                a/=j
n75 = 0
n25 = 0
n15 = 0
n5=0
n3 = 0 
for i in numbers.values():
    if i>=74:
        n75+=1
    if i>=24:
        n25+=1
    if i>=14:
        n15+=1
    if i>= 4:
        n5+=1
    if i>=2:
        n3+=1
ans = n75+n25*(n3-1)+n15*(n5-1)+n5*(n5-1)//2*(n3-2)
print(str(ans)+"\n")

Solution (Python):
from collections import Counter

n = int(input())

def prime_factorize(n):
    i = 2
    temp = n
    result = []
    while(i * i <= n):
        count = 0
        while temp % i == 0:
            count += 1
            temp //= i
        if count > 0:
            result.append([i, count])
        i += 1
    if temp != 1:
        result.append([temp, 1])
    return result

c = Counter()
for i in range(1, n + 1):
    pf = prime_factorize(i)
    for p in pf:
        c[p[0]] += p[1]

count2 = 0
count4 = 0
count15 = 0
count25 = 0
count75 = 0
for i, v in c.items():
    if v >= 74:
        count75 += 1
    if v >= 24:
        count25 += 1
    if v >= 14:
        count15 += 1
    if v >= 4:
        count4 += 1
    if v >= 2:
        count2 += 1


b = count4 * (count4 - 1) * (count2 - 2) // 2
c = count15 * (count4 - 1)
d = count25 * (count2 - 1)
e = count75


print(b + c + d + e)

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

def calc(p, N):
    ans = 0
    while N != 0:
        N //= p
        ans += N
    return ans

N = int(input())
P = primes(N)
count = []
for i in range(len(P)):
    count.append(calc(P[i], N))
ans = 0
for i in range(len(P)):
    if count[i] >= 74:
        ans += 1

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

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

print(ans)

Solution (Python):
N=int(input())
soinsu=[0]*N
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
for n in range(2,N+1):
  for a in factorization(n):
    soinsu[a[0]-1]+=a[1]
over2=0
over4=0
over14=0
over24=0
over74=0
for i in range(N):
  if soinsu[i]>=74:
    over74+=1
  if soinsu[i]>=24:
    over24+=1
  if soinsu[i]>=14:
    over14+=1
  if soinsu[i]>=4:
    over4+=1
  if soinsu[i]>=2:
    over2+=1
print(over74 + over24*(over2-1) + over14*(over4-1) + over4*(over4-1)*(over4-2)//2 + (over2-over4)*over4*(over4-1)//2)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()

d = [1 for _ in range(100)]

for i in range(1,N+1):
    j = 2
    while i > 1:
        if i % j == 0:
            d[j] += 1
            i //= j
        else:
            j += 1
n3 = 0
n5 = 0
n15 = 0
n25 = 0
n75 = 0
for x in d:
    if x >= 3: n3 += 1
    if x >= 5: n5 += 1
    if x >=15: n15 +=1
    if x >=25: n25 +=1
    if x >=75: n75 +=1
ans = (n3-n5) * ((n5) * (n5-1) // 2) + (n5) * (n5-1) * (n5-2) // 2
ans += (n5 - n15) * n15 + (n15) * (n15-1)
ans += (n3 - n25) * n25 + (n25) * (n25-1)
ans += n75
print (ans)

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

def solve(N):
    seventyfour = [78,101]
    twentyfour = [28,54,100,101]
    fourteen = [16,30,60,91,101]
    four = [6,9,20,28,44,52,68,76,92,116]
    two = [4,6,10,14,22,26,34,38,46,58,62,74,82,86,94,106]
    lists = [two,four,fourteen,twentyfour,seventyfour]
    nums = []
    for lis in lists:
        for i,n in enumerate(lis):
            if N<n:
                nums.append(i)
                break
    ans = nums[1]*(nums[1]-1)//2*(nums[0]-2)+nums[2]*(nums[1]-1)+nums[3]*(nums[0]-1)+nums[4]
    return ans
print(solve(N))

Solution (Python):
from itertools import product
from collections import defaultdict
n = int(input())


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


d = defaultdict(lambda: 0)
for i in range(2, n+1):
    a = factorization(i)
    for aa, k in a:
        d[aa] += k
t = [v for v in d.values()]


def num(t, a):
    return sum([1 if tt >= a-1 else 0 for tt in t])


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

Solution (Python):
def main():
    from collections import Counter

    N = int(input())

    p = [0] * (N + 1)
    for x in range(2, N + 1):
        d = 2
        cnt = 0
        while x % d == 0:
            x //= d
            cnt += 1
        p[d] += cnt

        d = 3
        while x > 1:
            cnt = 0
            while x % d == 0:
                x //= d
                cnt += 1
            p[d] += cnt
            d += 2

    ctr = Counter(p)

    def count(n):
        ret = 0
        for pw, cnt in ctr.items():
            if pw >= n - 1:
                ret += cnt
        return ret

    def choose(n, r):
        x, y = 1, 1
        for i in range(r):
            x *= n - i
            y *= i + 1
        return x // y

    ans = count(75)
    ans += count(25) * (count(3) - 1)
    ans += count(15) * (count(5) - 1)
    ans += choose(count(5), 2) * (count(3) - 2)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
exp = [0] * (N+1)
for i in range(2, N+1):
    cur = i
    for p in range(2, i+1):
        while cur % p == 0:
            exp[p] += 1
            cur //= p

def num(x):
    '''冪乗がx-1以上の数を返す'''
    return len(list(filter(lambda y: y >= x-1, exp)))

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

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
power = [0] * (N+1)
for x in range(2, N+1):
    for p in range(2, x+1):
        while x % p == 0:
            power[p] += 1
            x //= p

def num(x):
    '''約数がx-1以上の数を返す'''
    return len(list(filter(lambda y: y >= x-1, power)))

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

Solution (Python):
from collections import defaultdict

def dfs(i, comb):
    key = (i, comb)
    if key in memo:
        return memo[key]
    if comb == 75:
        return 1
    if i == m:
        return 0
    k, v = p[i]
    res = 0
    for j in range(v + 1):
        if comb * (j + 1) <= 75:
            res += dfs(i + 1, comb * (j + 1))
    memo[key] = res
    return res

n = int(input())
index = defaultdict(int)

for x in range(2, n + 1):
    y = 2
    while y ** 2 <= x:
        while x % y == 0:
            x //= y
            index[y] += 1
        y += 1
    if x > 1:
        index[x] += 1

*p, = index.items()
m = len(p)
memo = {}
print(dfs(0, 1))

Solution (Python):
from collections import defaultdict, deque, Counter
import sys
input = sys.stdin.readline


def getPrimes(n):
    isPrime = [True] * n
    ret = []
    for p in range(2, n):
        if not isPrime[p]:
            continue
        ret.append(p)
        for i in range(p, n, p):
            isPrime[i] = False
    return ret


def main():
    N = int(input())
    P = getPrimes(N)
    C = Counter()

    for i in range(1, N + 1):
        cnt = Counter()
        for p in P:
            while i % p == 0:
                i //= p
                cnt[p] += 1
        C += cnt

    d = {3: 0, 5: 0, 15: 0, 25: 0, 75: 0}
    for k in d.keys():
        for v in C.values():
            if v >= k - 1:
                d[k] += 1

    ans = 0
    ans += (d[5] * (d[5] - 1) // 2) * (d[3] - 2)
    ans += d[15] * (d[5] - 1)
    ans += d[25] * (d[3] - 1)
    ans += d[75]
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from math import factorial
from itertools import permutations

n=int(input())
np=factorial(n)
p_list=[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 s,t,u in permutations(p_list,3):
  num1=(s**4)*(t**4)*(u**2)
  num2=(s**14)*(t**4)
  num3=(s**24)*(t**2)
  num4=s**74
  for z in [num1,num2,num3,num4]:
    if np%z==0:
      ans.append(z)

print(len(set(ans)))

Solution (Python):
from math import factorial
from itertools import permutations

def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p, p_list

n=int(input())
np=factorial(n)

lim=10**2+1
is_p, p_list=eratosthenes(lim)

ans=[]
for s,t,u in permutations(p_list,3):
  num1=(s**4)*(t**4)*(u**2)
  num2=(s**14)*(t**4)
  num3=(s**24)*(t**2)
  num4=s**74
  for z in [num1,num2,num3,num4]:
    if np%z==0:
      ans.append(z)

print(len(set(ans)))

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

from collections import Counter
c=Counter(a)
c=c.most_common()
c3=0
c5=0
c15=0
c25=0
c75=0
for k,v in c:
  if 2<=v<4:c3+=1
  elif 4<=v<14:c5+=1
  elif 14<=v<24:c15+=1
  elif 24<=v<74:c25+=1
  elif 74<=v:c75+=1
c3=c3+c5+c15+c25+c75
c5=c5+c15+c25+c75
c15=c15+c25+c75
c25=c25+c75
ans=0
ans+=(c5*(c5-1)//2)*(c3-2)
ans+=c15*(c5-1)
ans+=c25*(c3-1)
ans+=c75
print(ans)

Solution (Python):
from math import factorial
from itertools import permutations

n=int(input())

np=factorial(n)

def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p, p_list

lim=10**2+1
is_p, p_list=eratosthenes(lim)

cnt=0
ans=[]
l=len(p_list)
for i in range(l):
  for j in range(i+1,l):
    for k in range(j+1,l):
      for s,t,u in permutations([p_list[i],p_list[j],p_list[k]],3):
        num1=(s**4)*(t**4)*(u**2)
        num2=(s**14)*(t**4)
        num3=(s**24)*(t**2)
        num4=s**74
        for z in [num1,num2,num3,num4]:
          if np%z==0:
            ans.append(z)

print(len(set(ans)))

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


def factorization(n: int):
    if n == 1:
        return []  
    
    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


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  


N = read_a_int()












N_fact = defaultdict(lambda: 0)
for i in ra(1, N + 1):
    tmp = factorization(i)
    for k, v in tmp:
        N_fact[k] += v

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


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





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

print(ans)

Solution (Python):
n = int(input())
if n == 1:
    print(0)
    exit()

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


pms = primes(n)
num = [0]*len(pms)
ans = 0
for j in range(2,n+1):
    for i in range(len(pms)):
        while j % pms[i] == 0:
            j //= pms[i]
            num[i] += 1
c74 = 0
c24 = 0
c14 = 0
c4 = 0
c2 = 0
for i in range(len(num)):
    if num[i] >= 74:
        c74 += 1
        c24 += 1
        c14 += 1
        c4 += 1
        c2 += 1
    elif num[i] >= 24:
        c24 += 1
        c14 += 1
        c4 += 1
        c2 += 1
    elif num[i] >= 14:
        c14 += 1
        c4 += 1
        c2 += 1
    elif num[i] >=4:
        c4 += 1
        c2 += 1
    elif num[i] >= 2:
        c2 += 1
ans += c74
ans += c24 * (c2-1)
ans += c14 * (c4-1)
ans += c4*(c4-1)//2 * (c2-2)
print(ans)

Solution (Python):
P = [1 for _ in range(100)]
P[0]=0
P[1]=0
for i in range(2,10):
    for j in range(i*i,100,i):
        P[j] = 0
Q = []
for i in range(100):
    if P[i]==1:
        Q.append(i)
C = {i:0 for i in Q}
N = int(input())
for i in range(2,N+1):
    x = i
    for p in C:
        while x%p==0:
            x = x//p
            C[p] += 1

c2 = 0
c4 = 0
for p in C:
    if 2<=C[p]<4:
        c2 += 1
    elif C[p]>=4:
        c4 += 1
cnt = c2*((c4*(c4-1))//2)+c4*(((c4-1)*(c4-2))//2)

c2 = 0
c24 = 0
for p in C:
    if 2<=C[p]<24:
        c2 += 1
    elif C[p]>=24:
        c24 += 1
cnt += c2*c24+c24*(c24-1)

c4 = 0
c14 = 0
for p in C:
    if 4<=C[p]<14:
        c4 += 1
    elif C[p]>=14:
        c14 += 1
cnt += c4*c14+c14*(c14-1)

c74 = 0
for p in C:
    if C[p]>=74:
        c74 += 1
cnt += c74
print(cnt)

Solution (Python):
def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes
N=int(input())
primes=get_primes(N)
numbers=[]
for i in primes:
  temp=0
  j=1
  while i**j<=N:
    temp+=N//(i**j)
    j+=1
  numbers.append(temp)
counter3=0
counter5=0
counter15=0
counter25=0
counter75=0
for i in numbers:
  if i>1:
    counter3+=1
  if i>3:
    counter5+=1
  if i>13:
    counter15+=1
  if i>23:
    counter25+=1
  if i>73:
    counter75+=1
print(counter75+(counter5-1)*counter15+(counter3-1)*counter25+(counter3-2)*(counter5-1)*counter5//2)

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

def getPrimes():
    isPrime = [True] * 100
    primes = []
    for p in range(2, 100):
        if not isPrime[p]:
            continue
        primes.append(p)
        for i in range(p, 100, p):
            isPrime[i] = False
    return primes

P = getPrimes()
A = Counter()

for n in range(1, N + 1):
    cnt = Counter()
    for p in P:
        while n % p == 0:
            n //= p
            cnt[p] += 1
    A += cnt

D = {3: 0, 5: 0, 15: 0, 25: 0, 75: 0}
for k in D.keys():
    for c in A.values():
        if (c + 1) >= k:
            D[k] += 1

ans = 0
ans += (D[5] * (D[5] - 1) // 2) * (D[3] - 2)
ans += D[15] * (D[5] - 1)
ans += D[25] * (D[3] - 1)
ans += D[75]
print(ans)

Solution (Python):
from collections import defaultdict

N = int(input())

dic = defaultdict(int)


def factoring(k): 
    import math
    n = int(math.sqrt(k))+2
    for i in range(2, n):
        count = 0
        while k%i == 0:
            count += 1
            k = k//i
        if count != 0:
            dic[i] += count
    if k != 1: 
        dic[k] += 1
    return

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

ans = 0
for i in dic:
    if dic[i] >= 74:
        ans += 1
    if dic[i] >= 2:
        count = 0
        for j in dic:
            if i == j:
                continue
            if dic[j] >= 4:
                count += 1
        ans += count * (count - 1) // 2
    if dic[i] >= 2:
        for j in dic:
            if i == j:
                continue
            if dic[j] >= 24:
                ans += 1
    if dic[i] >= 4:
        for j in dic:
            if i == j:
                continue
            if dic[j] >= 14:
                ans += 1

print (ans)

Solution (Python):

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

n = int(input())

from collections import defaultdict
dic = defaultdict(int)

for i in range(1, n+1):
    for prime in prime_decomposition(i):
        dic[prime] += 1

values = dic.values()

up2 = 0
up4 = 0
up14 = 0
up24 = 0
up74 = 0
for d in values:
    if d >= 74:
        up74 += 1
    if d >= 24:
        up24 += 1
    if d >= 14:
        up14 += 1
    if d >= 4:
        up4 += 1
    if d >= 2:
        up2 += 1






ans = 0

ans += up74

ans += up24 * (up2 - 1)

ans += up14 * (up4 - 1)

ans += up4 * (up4 - 1) * (up2-2) // 2


print(ans)

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

N = int(input())


exp = [0] * (N + 1)
primes = primes(N)
for n in range(2, N + 1):
    num = n
    for prime in primes:
        while num % prime == 0:
            exp[prime] += 1
            num //= prime

cnt = lambda X: len([e for e in exp if e >= X])

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

print(ans)

Solution (Python):

import sys
from collections import defaultdict
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

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 = ir()
dic = defaultdict(int)
for x in range(2, N+1):
    primes = prime_factorize(x)
    for p in primes:
        if p in dic:
            dic[p] += 1
        else:
            dic[p] = 1

answer = 0
for x, y, z in itertools.permutations(dic.values(), 3):
    if x >= 2 and y >= 4 and z >= 4:
        answer += 1

answer //= 2
for x, y in itertools.permutations(dic.values(), 2):
    if x >= 4 and y >= 14:
        answer += 1
    if x >= 2 and y >= 24:
        answer += 1

for x in dic.values():
    if x >= 74:
        answer += 1

print(answer)

Solution (Python):
n = int(input())
dic = {}
for i in range(2, n+1):
    num = i
    for j in range(2, num+1):
        c = 0
        while num%j==0:
            c += 1
            num //= j
        if c > 0:
            if j in dic:
                dic[j] += c
            else:
                dic[j] = c
t, f, ft, tw = 0,0,0,0
end = 0
for _i, j in dic.items():
    if j >= 2:
        t += 1
        if j >= 4:
            f += 1
            if j >= 14:
                ft += 1
                if j >= 24:
                    tw += 1
                    if j >= 74:
                        end += 1

result = 0

result += end

result += tw*(t-1)

result += ft*(f-1)

result += f*(f-1)*(t-2)//2

print(result)

Solution (Python):
n = int(input())
dic = {}
for i in range(2, n+1):
    num = i
    for j in range(2, num+1):
        c = 0
        while num%j==0:
            c += 1
            num //= j
        if c > 0:
            if j in dic:
                dic[j] += c
            else:
                dic[j] = c
t, f, ft, tw = 0,0,0,0
end = 0
for _i, j in dic.items():
    if j >= 2:
        t += 1
        if j >= 4:
            f += 1
            if j >= 14:
                ft += 1
                if j >= 24:
                    tw += 1
                    if j >= 74:
                        end += 1

result = 0

result += end

result += tw*(t-1)

result += ft*(f-1)

result += f*(f-1)*(t-2)//2

print(result)

Solution (Python):
n = int(input())
dict1 = {}
ans = 0


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

for i in range(1,n+1):
    t = prime_decomposition(i)
    for j in t:
        if j in dict1:
            dict1[j] += 1
        else:
            dict1[j] = 1

dict1_sorted = sorted(dict1.items(), key=lambda x:x[0])

li = []
for i in dict1_sorted:
    if i[1] >= 2:
        li.append(i)

m = len(li)

for i in li:
    if i[1] >= 74:
        ans += 1
    else:
        break

for i in li:
    for j in li:
        if i[0] != j[0]:
            if i[1] >= 2 and j[1] >= 24:
                ans += 1
            if i[1] >= 4 and j[1] >= 14:
                ans += 1

ans2 = 0

for i in li:
    for j in li:
        for k in li:
            if i[0] != j[0] and j[0] != k[0] and k[0] != i[0]:
                if i[1] >= 2 and j[1] >= 4 and k[1] >= 4:
                    ans2 += 1

ans += ans2 // 2

print(ans)

Solution (Python):

"""
約数の個数の求め方は、素因数分解した時の各要素の(乗数+1)をかけ合わせると求まる。
入力例2の32400を素因数分解してみると、
2^4*3^4*5^2となり、それぞれの乗数+1をかけ合わせると
(4+1)*(4+1)*(2+1) = 75となる。

また、75自体を素因数分解すると、
3^1*5^2となり、これが最小の約数であるので、
3*5*5
15*5
3*25
75
の4通りが素因数分解した時の乗数+1の候補として考えられる。

よって、約数が75個存在する数とは、基数をp,q,rとして,
p^(3-1)*q^(5-1)*r^(5-1)
p^(15-1)*q^(5-1)
p^(3-1)*q^(25-1)
p^(75-1)
のいずれかとして得られる数である。

なお、p^2*q^4*r^4の場合は4を2回使うため、combinationを使って数える必要があるのに注意。
"""
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
dic1 = defaultdict(int)

"""素因数分解"""
def factrize(n):
    b = 2
    fct = []
    while b*b <= n:
        while n % b == 0:
            n //= b
            
            """
            if not b in fct:
                fct.append(b)
            """
            fct.append(b)
        b = b+1
    if n > 1:
        fct.append(n)
    return fct 


def large_conbination(n,k): 
    res1 = 1
    for i in range(n,n-k,-1):
        res1*=i
    res2 = 1
    for i in range(1,k+1):
        res2*= i
    return res1//res2

for i in range(2,n+1): 
    for j in factrize(i):
        dic1[j] += 1

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


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

Solution (Python):
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():
    n = ni()

    e = [0] * (n + 1)

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

    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
    
    print(num(75) + num(25)*(num(3) - 1) + num(15)*(num(5) - 1)
        + num(5)*(num(5) - 1)*(num(3) - 2) // 2)


if __name__ == '__main__':
    main()

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





insuu=[0]*(100+1)
l=[]
sevenfour=0
twofour=0
onefour=0
four=0
two=0
for k in range(N):
    pf = {}
    m = k+1
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1: pf[m] = 1
    
    keys = list(pf.keys())
    values = list(pf.values())
    for i in range(len(keys)):
        insuu[keys[i]]=insuu[keys[i]]+values[i]
    

for i in range(101):
    if insuu[i]>=74:
        sevenfour = sevenfour+1
    if insuu[i]>=14:
        onefour=onefour+1
    if insuu[i]>=24:
        twofour=twofour+1
    if insuu[i]>=4:
        four=four+1
    if insuu[i]>=2:
        two=two+1
print(((four*(four-1))//2)*(two-2)+twofour*(two-1)+onefour*(four-1)+sevenfour)