Problem:


Score : 400 points

Problem Statement

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

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

Note

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

Constraints

1 \leq N \leq 100

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

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

Sample Input 1

9

Sample Output 1

0

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

Sample Input 2

10

Sample Output 2

1

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

Sample Input 3

100

Sample Output 3

543



Sample input:
9


Sample output:
0

Submission status: Accepted

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if n <= 0: return 0
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p;
            for k in range(p-1,r,p):
                numerator[k - offset] //= pivot
                denominator[k] //= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

a = int(input())

b = [0 for i in range(15)]
j = 0
c = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
d = [0 for i in range(101)]
p = 0
pp = 0
g = 0
gg = 0
ggg = 0
co = 0
for i in range(1,101):
  k = i
  while True:
    if k % c[j] == 0 and k >= c[j]:
      b[j] += 1
      k //= c[j]
    else:
      j += 1
      if j == 15:
        j = 0
        break
  for k in range(15):
    if b[k] >= 74:
      g += 1
    if b[k] >= 24:
      gg += 1
    if b[k] >= 14:
      ggg += 1
    if b[k] >= 4:
      p += 1
    if b[k] >= 2:
      pp += 1
  if i >= 10:
    d[i] = cmb(p, 2)*cmb((pp-2), 1) + cmb(g, 1) + cmb(gg, 1)*cmb((pp-1), 1) + cmb(ggg, 1)*cmb((p-1), 1)
  p = 0
  pp = 0
  g = 0
  gg = 0
  ggg = 0
print(d[a])

Submission status: Accepted

Solution code:
def comb(n, k):
    k = min(k, n - k)
    ans = 1
    for i in range(n, n - k, -1):
        ans *= i
    for i in range(1, k + 1):
        ans //= i 
    return ans

def getNum(n,t) :
    s=0
    I=n
    R=n

    count = 1

    while s==0:
        for i in range(2,R+1):
            if I%i==0:
                I=I/i
                if I==1:
                    s=1
                if i in t:
                    t[i] = t[i] + 1
                else : 
                    t[i] = 1                
                count += 1
                break
    return count    

n = int(input())
t = {}

yaku = 1
for i in range(2,n+1):
    yaku = yaku + getNum(i,t)

#print(t)

ans = 0
n5 = 0
n3 = 0
for v in t.values():
    if v >= 4:
        n5 += 1
    if v >= 2:
        n3 += 1

if(n5 >= 2 and n3 >= 3):
    ans += comb(n5,2)*comb(n3-2,1)

n5 = 0
n3 = 0
for v in t.values():
    if v >= 14:
        n5 += 1
    if v >= 4:
        n3 += 1
#print(n5,n3)
ans += n5*(n3-1)

n5 = 0
n3 = 0
for v in t.values():
    if v >= 24:
        n5 += 1
    if v >= 2:
        n3 += 1
#print(n5,n3)
ans += n5*(n3-1)

n5 = 0
n3 = 0
for v in t.values():
    if v >= 74:
        n5 += 1
#print(n5)
ans += n5

print(ans)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


a = int(input())

b = [0 for i in range(15)]
j = 0
c = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
d = [0 for i in range(101)]
p = 0
pp = 0
g = 0
gg = 0
ggg = 0
co = 0
for i in range(1,101):
  k = i
  while True:
    if k % c[j] == 0 and k >= c[j]:
      b[j] += 1
      k //= c[j]
    else:
      j += 1
      if j == 15:
        j = 0
        break
  for k in range(15):
    if b[k] >= 74:
      g += 1
    if b[k] >= 24:
      gg += 1
    if b[k] >= 14:
      ggg += 1
    if b[k] >= 4:
      p += 1
    if b[k] >= 2:
      pp += 1
  if i >= 10:
    d[i] = cmb(p, 2)*cmb((pp-2), 1) + cmb(g, 1) + cmb(gg, 1)*cmb((pp-1), 1) + cmb(ggg, 1)*cmb((p-1), 1)
  p = 0
  pp = 0
  g = 0
  gg = 0
  ggg = 0
print(d[a])

Submission status: Accepted

Solution code:
from math import factorial as f

N = int(input())

primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
divs = []
for i in range(1,101):
    tmp = [0 for _ in range(len(primes))]
    for j in range(len(primes)):
        p = primes[j]
        tmp[j] = 0
        while(i//p==i/p):
            i = i//p
            tmp[j] += 1
    divs.append(tmp)
#print(divs)

divsum = [0 for _ in range(len(primes))]
for i in range(1, N+1):
    for j in range(len(primes)):
        divsum[j] += divs[i-1][j]
#print(divsum)

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

ans = 0

# >=74
ans += num(75)

# >=14 & 13~4
ans += num(15)*(num(5)-1)

# >=24 & 23~2
ans += num(25)*(num(3)-1)

# >=4,>=4 & >=2
ans += num(5) * (num(5)-1) * (num(3)-2) // 2 
print(int(ans))

Submission status: Accepted

Solution code:
n=int(input())
primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
pcnt = [0]*len(primes)
for x in range(1,n+1):
  for pidx in range(len(primes)):
    p=primes[pidx]
    while x % p ==0:
      x//=p
      pcnt[pidx]+=1
      
ret=0
#3*5*5 case
for i in range(len(pcnt)):
  for j in range(i+1,len(pcnt)):
    for k in range(len(pcnt)):
      if pcnt[i]>=4 and pcnt[j]>=4 and pcnt[k]>=2 and i!=k and j!=k:
        ret+=1
#3*25 case
for i in range(len(pcnt)):
  for j in range(len(pcnt)):
    if pcnt[i]>=24 and pcnt[j]>=2 and i!=j:
      ret+=1
#5*15 case
for i in range(len(pcnt)):
  for j in range(len(pcnt)):
    if pcnt[i]>=14 and pcnt[j]>=4 and i!=j:
      ret+=1
#75 case
for i in range(len(pcnt)):
  if pcnt[i]>=74:
    ret+=1

print(ret)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
pcnt = [0]*len(primes)
for x in range(1,n+1):
  for pidx in range(len(primes)):
    p=primes[pidx]
    while x % p ==0:
      x//=p
      pcnt[pidx]+=1

primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
pcnt = [0]*len(primes)
for x in range(1,n+1):
  for pidx in range(len(primes)):
    p=primes[pidx]
    while x % p ==0:
      x//=p
      pcnt[pidx]+=1
      
ret=0
#3*5*5 case
for i in range(len(pcnt)):
  for j in range(i+1,len(pcnt)):
    for k in range(len(pcnt)):
      if pcnt[i]>=4 and pcnt[j]>=4 and pcnt[k]>=2 and i!=k and j!=k:
        ret+=1
#3*25 case
for i in range(len(pcnt)):
  for j in range(len(pcnt)):
    if pcnt[i]>=24 and pcnt[j]>=2 and i!=j:
      ret+=1
#5*15 case
for i in range(len(pcnt)):
  for j in range(len(pcnt)):
    if pcnt[i]>=14 and pcnt[j]>=4 and i!=j:
      ret+=1
#75 case
for i in range(len(pcnt)):
  if pcnt[i]>=74:
    ret+=1

print(ret)

Submission status: Accepted

Solution code:
N = int(input())

prime = [0] * 101

for i in range(2, N + 1):
    temp = i

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

        if temp == 1:
            break

ans = 0

for i in range(2, N + 1):
    temp1 = prime[i]

    if temp1 == 0:
        continue
    
    if temp1 >= 74:
        ans += 1
    
    for j in range(i + 1, N + 1):
        temp2 = prime[j]

        if temp2 == 0:
            continue
        
        temp_list = [temp1, temp2]

        order1 = [0, 1]
        order2 = [1, 0]

        for h in range(2):
            if temp_list[order1[h]] >= 4 and temp_list[order2[h]] >= 14:
                ans += 1

            if temp_list[order1[h]] >= 2 and temp_list[order2[h]] >= 24:
                ans += 1
        
        for k in range(j + 1, N + 1):
            temp3 = prime[k]

            if temp3 == 0:
                continue
            
            temp_list = [temp1, temp2, temp3]

            order1 = [0, 1, 2]
            order2 = [1, 2, 0]
            order3 = [2, 0, 1]

            for h in range(3):
                if temp_list[order1[h]] >= 2 and temp_list[order2[h]] >= 4 and temp_list[order3[h]] >= 4:
                    ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

def factorial(n):
    a = 1
    for i in range(1, n+1):
        a *= i
    return a

def comb(n,r):
    if r <= 0:
        return 1
    return factorial(n) // (factorial(n-r) * factorial(r))

ans = 0
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
pp = [[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [4, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [3, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], [2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [3, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [2, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], [4, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0], [2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [3, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [5, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
ppp = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [3, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [4, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [4, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [7, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [7, 4, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [8, 4, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [8, 4, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [10, 5, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [10, 5, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [11, 5, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [11, 6, 3, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [15, 6, 3, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [15, 6, 3, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [16, 8, 3, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [16, 8, 3, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [18, 8, 4, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [18, 9, 4, 3, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [19, 9, 4, 3, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [19, 9, 4, 3, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [22, 10, 4, 3, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [22, 10, 6, 3, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [23, 10, 6, 3, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [23, 13, 6, 3, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [25, 13, 6, 4, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [25, 13, 6, 4, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [26, 14, 7, 4, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [26, 14, 7, 4, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [31, 14, 7, 4, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [31, 15, 7, 4, 3, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [32, 15, 7, 4, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [32, 15, 8, 5, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [34, 17, 8, 5, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [34, 17, 8, 5, 3, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [35, 17, 8, 5, 3, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [35, 18, 8, 5, 3, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [38, 18, 9, 5, 3, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [38, 18, 9, 5, 3, 3, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [39, 19, 9, 6, 3, 3, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [39, 19, 9, 6, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [41, 19, 9, 6, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [41, 21, 10, 6, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [42, 21, 10, 6, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [42, 21, 10, 6, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [46, 22, 10, 6, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [46, 22, 10, 8, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [47, 22, 12, 8, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [47, 23, 12, 8, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [49, 23, 12, 8, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [49, 23, 12, 8, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [50, 26, 12, 8, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [50, 26, 13, 8, 5, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [53, 26, 13, 9, 5, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [53, 27, 13, 9, 5, 4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [54, 27, 13, 9, 5, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [54, 27, 13, 9, 5, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], [56, 28, 14, 9, 5, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], [56, 28, 14, 9, 5, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], [57, 28, 14, 9, 5, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], [57, 30, 14, 10, 5, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], [63, 30, 14, 10, 5, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], [63, 30, 15, 10, 5, 5, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], [64, 31, 15, 10, 6, 5, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], [64, 31, 15, 10, 6, 5, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0], [66, 31, 15, 10, 6, 5, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0], [66, 32, 15, 10, 6, 5, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0], [67, 32, 16, 11, 6, 5, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0], [67, 32, 16, 11, 6, 5, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0], [70, 34, 16, 11, 6, 5, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0], [70, 34, 16, 11, 6, 5, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0], [71, 34, 16, 11, 6, 5, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0], [71, 35, 18, 11, 6, 5, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0], [73, 35, 18, 11, 6, 5, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0], [73, 35, 18, 12, 7, 5, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0], [74, 36, 18, 12, 7, 6, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0], [74, 36, 18, 12, 7, 6, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0], [78, 36, 19, 12, 7, 6, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0], [78, 40, 19, 12, 7, 6, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0], [79, 40, 19, 12, 7, 6, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0], [79, 40, 19, 12, 7, 6, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0], [81, 41, 19, 13, 7, 6, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0], [81, 41, 20, 13, 7, 6, 5, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0], [82, 41, 20, 13, 7, 6, 5, 4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0], [82, 42, 20, 13, 7, 6, 5, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0], [85, 42, 20, 13, 8, 6, 5, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0], [85, 42, 20, 13, 8, 6, 5, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], [86, 44, 21, 13, 8, 6, 5, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], [86, 44, 21, 14, 8, 7, 5, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], [88, 44, 21, 14, 8, 7, 5, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], [88, 45, 21, 14, 8, 7, 5, 4, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], [89, 45, 21, 14, 8, 7, 5, 4, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], [89, 45, 22, 14, 8, 7, 5, 5, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], [94, 46, 22, 14, 8, 7, 5, 5, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], [94, 46, 22, 14, 8, 7, 5, 5, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [95, 46, 22, 16, 8, 7, 5, 5, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [95, 48, 22, 16, 9, 7, 5, 5, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [97, 48, 24, 16, 9, 7, 5, 5, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

p = ppp[n-1]

i2, i4, i14, i24, i74 = 0,0,0,0,0
for x in p:
    if 2 <= x < 4:
        i2 += 1
    elif 4 <= x < 14:
        i4 += 1
    elif 14 <= x < 24:
        i14 += 1
    elif 24 <= x < 74:
        i24 += 1
    elif 74 <= x:
        i74 += 1
    else:
        pass

ans = 0
#1
ans += comb(i4+i14+i24+i74, 3) * 3
ans += comb(i4+i14+i24+i74, 2) * i2

#2
ans += comb(i14+i24+i74, 2) * 2
ans += (i14+i24+i74) * i4

#3
ans += comb(i24+i74, 2) * 2
ans += (i24+i74) * (i2+i4+i14)

#4
ans += i74

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
class Prime:
    def __init__(self,number):#N以下の素数
        self.jud=[True]*(number+5)
        self.pri=[]
        self.jud[0]=False
        self.jud[1]=False
        for i in range(number):
            if self.jud[i]:
                self.pri.append(i)
                for j in range(2,(number)//i+1):
                    self.jud[i*j]=False
    
    def judge(self,x):
        return self.jud[x]
    
    def decom(self,x):
        s=x
        a =defaultdict(int)
        if s==1:
            return a
        while s>1:
            for p in self.pri:
                if s%p==0:
                    a[p]+=1
                    s=s//p
                    break
        return a
            

A=Prime(102+5)
N=int(input())
dd=defaultdict(int)
for s in range(2,N+1):
    d1=A.decom(s)
    for p,v in d1.items():
        dd[p]+=v
ans=0
#3-5-5type
L=[0,0]
for p,v in dd.items():
    if 2<=v<4:
        L[0]+=1
    elif 4<=v:
        L[1]+=1
ans+=(L[0]*L[1]*max(L[1]-1,0))//2
ans+=(L[1]*max(L[1]-1,0)*max(L[1]-2,0))//2
#print(ans)
#15-5type
M=[0,0]
for p,v in dd.items():
    if 4<=v<14:
        M[0]+=1
    elif 14<=v:
        M[1]+=1
ans+=M[0]*M[1]
ans+=(M[1]*max(M[1]-1,0))
#print(ans)
#25-3type
N=[0,0]
for p,v in dd.items():
    if 2<=v<24:
        N[0]+=1
    elif 24<=v:
        N[1]+=1
ans+=N[0]*N[1]
ans+=(N[1]*max(N[1]-1,0))
for p,v in dd.items():
    if 74<=v:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
q=[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())
p={}
for i in range(N):
 n=i+1
 for j in range(25):
  if n==1 or n<q[j]:break
  while n%q[j]==0:p[q[j]]=1if q[j]not in p.keys()else p[q[j]]+1;n//=q[j]
n=[1,3,13,23,73]
m=[len([v for v in p.values()if v>k])for k in n]
print(m[1]*~-m[1]//2*(m[0]-2)+m[3]*~-m[0]+m[2]*~-m[1]+m[4])

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter

def primes(x):
    d = {}
    i = 2
    while i <= x:
        count = 0
        while x % i == 0 and x > 0:
            count += 1
            x //= i
        if count > 0:
            d[i] = count
        i += 1
    return d


if __name__ == '__main__':
    n = int(input())
    d = {}
    for i in range(2, n + 1):
        d1 = primes(i)
        for j, v in d1.items():
            if j not in d:
                d[j] = v
            else:
                d[j] += v
    counter = Counter(d.values())
    d2 = {3: 0, 5: 0, 15: 0, 25: 0, 75: 0}
    for count, v in counter.items():
        if count >= 74:
            d2[75] += v
        if count >= 24:
            d2[25] += v
        if count >= 14:
            d2[15] += v
        if count >= 4:
            d2[5] += v
        if count >= 2:
            d2[3] += v
    ans = d2[75] + d2[25] * (d2[3] - 1) + d2[15] * (d2[5] - 1) + d2[5] * (d2[5] - 1) * (d2[3] - 2) // 2
    print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import Counter

def factorize(n: int):
    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


# 各階乗での素因数リストを出す。
n = ni()
divs = Counter()
for i in range(2,n+1):
    divs += factorize(i)
    


ans = 0
# 4,4,2以上を満たすペアを探す
gteq4 = []
lt4gteq2 = []
for k,v in divs.items():
    if v >= 4:
        gteq4.append(k)
    elif 2 <= v < 4:
        lt4gteq2.append(k)
        

# 4,4,4以上のみ
len_gteq4 = len(gteq4)
if len_gteq4 >= 3:
    ans += (len_gteq4*(len_gteq4-1)*(len_gteq4-2) // 6) * 3

# 4,4,2or3のみ
len_lt4gteq2 = len(lt4gteq2)
if len_gteq4 >= 2 and len_lt4gteq2 >= 1:
    ans += (len_gteq4*(len_gteq4-1)//2) * len_lt4gteq2
    
    
# 2,24以上を満たすペアを探す
gteq24 = []
gteq2 = []
for k,v in divs.items():
    if v >= 24:
        gteq24.append(k)
    if v >= 2:
        gteq2.append(k)
        
ans += (len(gteq24) * len(gteq2) - len(gteq24))


# 4,14以上を満たすペアを探す
gteq14 = []
for k,v in divs.items():
    if v >= 14:
        gteq14.append(k)

ans += (len(gteq14) * len(gteq4) - len(gteq14))


# 74以上のものを探す
gteq74 = []
for k,v in divs.items():
    if v >= 74:
        gteq74.append(k)
        
ans += len(gteq74)
        
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

sosus = [2]
for n in range(3, N + 1):
    is_sosu = True
    for s in sosus:
        if n % s == 0:
            is_sosu = False
            break
    if is_sosu: sosus.append(n)

soinsus = dict([[s, 1] for s in sosus])
for n in range(1, N + 1):
    for s in sosus:
        for n_pow in range(1, 10):
            if n % (s ** n_pow) != 0:
                break
        soinsus[s] += n_pow - 1

soinsu_pows = list(soinsus.values())

def upper_n(n_min):
    return len([sp for sp in soinsu_pows if sp >= n_min])

n_75 = 0
n_75 += upper_n(75)
n_75 += upper_n(25) * (upper_n(3) - 1)
n_75 += upper_n(15) * (upper_n(5) - 1)
n_75 += int(upper_n(5) * (upper_n(5) - 1) / 2 * (upper_n(3) - 2))

print(n_75)

Submission status: Accepted

Solution code:
import math
import collections

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:
        n = int(n)
        table.append(n)
    return table

def num(y):
    count = 0
    for i in x:
        if x[i] >= y:
            count += 1
    return count

N = int(input())
li = []
for i in range(1, N+1):
    li += prime_decomposition(i)
# print(collections.Counter(li))
x = collections.Counter(li)
ans = num(74) + num(24) * (num(2) - 1) + num(14) * (num(4) - 1)  + num(4) * (num(4) - 1) * (num(2) - 2) // 2
print(ans)