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:
# 75数を列挙して、N!を割り切れるかどうかで判定
from math import factorial, sqrt


def comb(n, r):  # n個からr個選ぶ場合の数
    if n < r:
        return 0
    else:
        return factorial(n)//(factorial(r) * factorial(n-r))


N = int(input())
fact = [0]*(N+1)
# それぞれを素因数分解
for i in range(2, N + 1):
    for j in range(2, i+1):
        while i % j == 0:
            i //= j
            fact[j] += 1
over4 = 0
over2 = 0
over24 = 0
over14 = 0
over74 = 0
for f in fact:
    if f >= 2:
        if f >= 4:
            over4 += 1
            if f >= 14:
                over14 += 1
            if f >= 24:
                over24 += 1
            if f >= 74:
                over74 += 1
        else:
            over2 += 1
ans = (comb(over4, 2) * over2) + comb(over4, 3) * 3 + \
    (over14) * (over4 - 1) + over24 * ((over4 - 1) + (over2)) + over74

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    if x!=1:
      retlist.append(x)
    return retlist

N=int(input())

if N==1:
  print(0)
  exit()

cnt=Counter()
for i in range(N):
  a=get_factors(i+1)
  acounter=Counter(a)
  cnt=cnt+acounter
values,counts=zip(*cnt.most_common())
ans=0
five=0
three=0
sevfou=0
twofou=0
fourteen=0
for c in counts:
  if c>=74:
    sevfou+=1
  if c>=24:
    twofou+=1
  if c>=14:
    fourteen+=1
  if c>=4:
    five+=1
  if c>=2:
    three+=1
ans+=(five*(five-1)/2)*(three-2)
ans+=(fourteen*(five-1))
ans+=(twofou*(three-1))
ans+=(sevfou)
print(int(ans))

Submission status: Accepted

Solution code:
n = int(input())
p_100 = [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]
p_n = []
for i in p_100:
  if i <= n:
    p_n.append(i)

# xはyで何回割れるか
class Div:
  def __init__(self):
    self.ans = 0
    self.ret = 0
    
  def divi(self,x,y):
    if x % y == 0:
      self.ans += 1
      return self.divi(x//y,y)
    else:
      self.ret = self.ans
      self.ans = 0
      return self.ret

Di = Div()

facto_n = [0] * 100 # facto_n[i] にn!を素因数分解した時のiの指数を格納
for i in range(1,n+1):
  for p in p_n:
    facto_n[p] += Di.divi(i,p)

#７５数が４パターンに分けられることに注意
f2, f4, f14, f24, f74 = 0, 0, 0, 0, 0
for i in range(1,100):
  if facto_n[i] >= 2:
    f2 += 1
  if facto_n[i] >= 4:
    f4 += 1
  if facto_n[i] >= 14:
    f14 += 1
  if facto_n[i] >= 24:
    f24 += 1
  if facto_n[i] >= 74:
    f74 += 1

ans = 0
if f4 >= 2 and f2 >= 3:
  ans += f4*(f4-1) // 2 * (f2-2)
if f14 >= 1 and f4 >= 2:
  ans += f14 * (f4-1)
if f24 >= 1 and f2 >= 2:
  ans += f24 * (f2-1)
if f74 >= 1:
  ans += f74

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

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()
prime_counter = Counter()

for i in range(2, n+1):
    primes = factorize(i)
    prime_counter += primes

# カウント
gteq74 = 0
gteq24 = 0
gteq14 = 0
gteq4 = 0
gteq2 = 0
gteq2_and_lt4 = 0
for _, cnt in prime_counter.items():
    gteq74 += 1 if cnt >= 74 else 0
    gteq24 += 1 if cnt >= 24 else 0
    gteq14 += 1 if cnt >= 14 else 0
    gteq4 += 1 if cnt >= 4 else 0
    gteq2 += 1 if cnt >= 2 else 0
    gteq2_and_lt4 += 1 if 2 <= cnt < 4 else 0

ans = gteq74 + (gteq24*gteq2 - gteq24) + (gteq14*gteq4 - gteq14)
ans += gteq4 * (gteq4-1) * (gteq4-2) // 2 + gteq4 * (gteq4-1) * gteq2_and_lt4 // 2

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
pdic= [0]*(101) #素因数分解
for i in range(2,n+1):
    cur = i
    for j in range(2,i+1):
        while cur % j == 0:
            pdic[j] += 1
            cur //= j

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

Submission status: Accepted

Solution code:
# 75=1*75=3*25=5*15=3*5*5
from math import factorial
from collections import Counter
from itertools import permutations


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


n = int(input())
ans1, ans2, ans3 = 0, 0, 0
primes = prime_factorization(factorial(n))
c = Counter(primes)
for key, count in c.items():
    if count >= 74:
        ans1 += 1
for item in permutations(c.items(), 2):
    key1, count1 = item[0]
    key2, count2 = item[1]
    if count1 >= 24 and count2 >= 2:
        ans2 += 1
    if count1 >= 14 and count2 >= 4:
        ans2 += 1
for item in permutations(c.items(), 3):
    key1, count1 = item[0]
    key2, count2 = item[1]
    key3, count3 = item[2]
    if count1 >= 4 and count2 >= 4 and count3 >= 2:
        ans3 += 1
print(ans1 + ans2 + ans3 // 2)

Submission status: Accepted

Solution code:
N = int(input())
seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
prime_map = {}
for prime in seed_primes:
    prime_map[prime] = 0


for i in range(2, N+1):
    _i = i
    for prime in seed_primes:
        while _i % prime == 0:
            prime_map[prime] += 1
            _i = _i // prime

reduced_prime_map = {}
for k, v in prime_map.items():
    if v > 0:
        reduced_prime_map[k] = v

prime_list = list(reduced_prime_map.values())



def dfs(n, res):
    global count
    if res == 75:
        count += 1
        return
    if res > 75:
        return
    if n == len(prime_list):
        return

    for thres in [0, 2, 4, 14, 24, 74]:
        if prime_list[n] >= thres:
            dfs(n + 1, res*(thres+1))

count = 0
dfs(0, 1)
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def prime_table(n):
    t = [True] * (n + 1)
    t[0] = False
    t[1] = False

    i = 2
    while i * i <= n:
        for ii in range(2 * i, n + 1, i):
            t[ii] = False
        i += 1
    return [x for x, i in enumerate(t) if i == True]


def solve(N: int):
    t = prime_table(100)

    ds = defaultdict(int)
    for i in range(1, N+1):
        for j in t:
            while i % j == 0:
                ds[j] += 1
                i = i // j

    ret = 0
    fs = list(ds.keys())
    for pi in range(len(fs)):
        p = ds[fs[pi]]
        if 74 <= p:
            ret += 1
        for qi in range(pi + 1, len(fs)):
            q = ds[fs[qi]]
            for cs in [[14, 4], [24, 2]]:
                if cs[0] <= p and cs[1] <= q:
                    ret += 1
                if cs[1] <= p and cs[0] <= q:
                    ret += 1
            for ri in range(qi + 1, len(fs)):
                r = ds[fs[ri]]
                if 2 <= p and 4 <= q and 4 <= r:
                    ret += 1
                if 4 <= p and 2 <= q and 4 <= r:
                    ret += 1
                if 4 <= p and 4 <= q and 2 <= r:
                    ret += 1
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    result = solve(N)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
pli = [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]
soli = []
it = []
for i in range(100):
    k = i+1
    so = [0]*(len(pli))
    for m in range(len(pli)):
        for j in range(8):
            if (k%pli[m])==0:
                so[m]+=1
                k//=pli[m]
            else:
                break
    soli.append(so)
N=int(input())
ssum = [ sum([ soli[i][m] for i in range(N) ]) for m in  range(len(pli))]

#4izyo: 9
#2-3 : 6
# 4izyo * 4izyo * 4izyo -> 9 * 8 * 7
# 4izyo * 4izyo * 2-3 -> 9 * 8 * 6
# 9*8*7/(3*2*1)+(9*8)/(2*1)*6

def getAB(a,b):
    return sum(map( lambda x:x>=a and b>=x ,ssum ))
def getC(a,r):
    if (a<=0):
        return 0
    if (r==1):
        return a
    else:
        return a * getC(a-1,r-1)
s = 0
s += max(getC(getAB(4,1000),3)//2,0)
s += max(getC(getAB(4,1000),2)//2*getAB(2,3),0)
s += max(getC(getAB(24,1000),2),0)
s += max(getAB(24,1000)*getAB(2,23),0)
s += max(getC(getAB(14,1000),2),0)
s += max(getAB(14,1000)*getAB(4,13),0)
s += max(getAB(74,1000),0)
print (s)

Submission status: Accepted

Solution code:
n=int(input())
P=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
D=dict()
for p in P:
  count=0
  order=1
  while p**order<=n:
    count+=n//(p**order)
    order+=1
  D[p]=count
List=[0 for i in range(5)]
for p in P:
  if D[p]>=74:
    List[4]+=1
  elif D[p]>=24:
    List[3]+=1
  elif D[p]>=14:
    List[2]+=1
  elif D[p]>=4:
    List[1]+=1
  elif D[p]>=2:
    List[0]+=1
for i in range(4):
  List[3-i]+=List[4-i]
print(List[4]+(List[0]-1)*List[3]+(List[1]-1)*List[2]+(List[0]-2)*List[1]*(List[1]-1)//2)

Submission status: Accepted

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

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


def num(m):  # e の要素のうち m-1 以上のものの個数
    return len(list(filter(lambda x: x >= m - 1, e)))


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

Submission status: Accepted

Solution code:
import math

n = int(input())
# 75数=約数の数が75個
# 約数の個数->n=Πp_m^a_mと表せるとき、Π(a_m+1)
# 75=5^3より、a_1=74またはa_1=24,a_2=2またはa_1=14,a_2=4またはa_1=4,a_2=4,a_3=4の場合に75数となる.
# ここで階乗n!の素因数分解した際の素因数pの個数に関しては、ガウス数[a]を用いて、Σ[n/p^k]で求められる.
# よって、Σ[n/p^k]>=4となるようなpがいくつあるかに注目すればよい.また、Σ[n/p^k]>=2,n<=100より、p=50まで調べればよい.
prime_list = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
over_2 = []
over_4 = []
over_14 = []
over_24 = []
over_74 = []
answer = 0
for prime_number in prime_list:
    prime_count = 0
    chk_number = prime_number
    while True:
        prime_count += n // chk_number
        chk_number *= prime_number
        if chk_number > n:
            break
    if prime_count >= 2:
        over_2.append(prime_number)
    if prime_count >= 4:
        over_4.append(prime_number)
    if prime_count >= 14:
        over_14.append(prime_number)
    if prime_count >= 24:
        over_24.append(prime_number)
    if prime_count >= 74:
        over_74.append(prime_number)
# 74個以上含まれる素因数が存在するとき.その素因数を74個使用した約数が75数になる.
answer += len(over_74)
# 24個以上含まれる素因数が存在し、かつ2個以上の素因数がそれ以外に存在するとき、それぞれを使用した約数が75数になる.
# over_24にある素因数は必ずもover_4に含まれることに注意.
answer += len(over_24) * (len(over_2) - 1)
# 14個以上含まれる素因数が存在し、かつ4個以上の素因数がそれ以外に存在するとき、それぞれを使用した約数が75数になる.
# over_24にある素因数は必ずもover_4に含まれることに注意.
answer += len(over_14) * (len(over_4) - 1)
# 4個以上含まれる素因数が2種類存在し、かつ2個以上の素因数がそれ以外に存在するとき、それぞれを使用した約数が75数になる.
# over_4にある素因数は必ずover_2に含まれることに注意.
answer += (len(over_4) * (len(over_4) - 1) // 2) * (len(over_2) - 2)

print(answer)

Submission status: Accepted

Solution code:
from collections import Counter
N=int(input())
fac=[]
for n in range(2, N+1):
	for x in range(2, int(n**0.5)+2):
		while n % x == 0:
			fac.append(x)
			n //= x
	if n > 1:
		fac.append(n)
c=Counter(fac)
cn=[len(list(filter(lambda x: x >= i, c.values()))) for i in range(75)]
print(cn[74] + cn[24] * (cn[2] - 1) + cn[14] * (cn[4] - 1) + cn[4] * (cn[4] - 1) * (cn[2] - 2) // 2)

Submission status: Accepted

Solution code:
N = int(input())
# N = 100
# 素因数を足し合わせてみる
divisors = [0]*(N+1)
# 素因数分解(小さい方から順に割っていく)
for j in range(2,N+1):
    s = 0
    L = j
    while s == 0:
        for i in range(2,N+1):
            if L % i == 0:
                divisors[i] += 1
                L //= i
                if L == 1:
                    s = 1 #1はこれ以上素因数を産まない
                break
    # print("{}!:{}".format(j,divisors))

# 3パターン
# 75　*　1 パターン
# 25 * 3 パターン
# 5 * 15 パターン
# 5 * 5 * 3 パターン
list75 = [i for i,div in enumerate(divisors) if 74 <= div and i > 1]
list25 = [i for i,div in enumerate(divisors) if 24 <= div and i > 1]
list15 = [i for i,div in enumerate(divisors) if 14 <= div and i > 1]
list5 = [i for i,div in enumerate(divisors) if 4 <= div and i > 1]
list3 = [i for i,div in enumerate(divisors) if 2 <= div and i > 1]
# list2 = [i for i,div in enumerate(divisors) if 1 <= div and i > 1]
# print(list75)
# print(list25)
# print(list15)
# print(list5)
# print(list3)
# print(len(list75),len(list25),len(list15),len(list5),len(list3))
n75 = len(list75)
n25 = len(list25)
n15 = len(list15)
n5 = len(list5)
n3 = len(list3)
print(n75 + n25*(n3-1) + n15*(n5-1) + n5*(n5-1)//2*(n3-2))

Submission status: Accepted

Solution code:
N = int(input())


prime = [2,3,5]

def isPrime(n):
    if n == 1:
        return False

    if n == 2 or n==3 or n==5:
        return True

    for div in prime:
        if n % div == 0:
            return False
    
    prime.append(n)
    return True

for x in range(1, N+1):
    isPrime(x)


#%%
def factoring(n):

    for div in prime:
        if div > n:
            break

        while n % div == 0:
            part[div] += 1
            n /= div

#%%
part = {x:0 for x in prime}
for x in range(1, N+1):
    factoring(x)

use = {3:0, 5:0, 15:0, 25:0, 75:0}
for x in part:
    if part[x] >= 2:
        use[3] += 1
    if part[x] >= 4:
        use[5] += 1
    if part[x] >= 14:
        use[15] += 1
    if part[x] >= 24:
        use[25] += 1
    if part[x] >= 74:
        use[75] += 1

ans = 0
# 75 = 75 * 1
if 75 in use:
    ans += use[75]
# 75 = 25 * 3
if 25 in use:
    ans += use[25] * (use[3] - 1)
# 75 = 15 * 5
if 15 in use:
    ans += use[15] * (use[5] - 1)
# 75 = 5 * 5 * 3
if 5 in use:
    ans += use[5] * (use[5] - 1) / 2 * (use[3] - 2)

print(int(ans))

Submission status: Accepted

Solution code:
def factoring(n):
    for i in range(2, n+1):
        while n % i == 0:
            n //= i
            d[i] += 1

N = int(input())

d = [0]*(N+1)

for n in range(2,N+1):
    factoring(n)

def num(n):
    return len([e for e in d if e >= n])

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

Submission status: Accepted

Solution code:
from math import factorial

N = int(input())

def prime_decomposition(n):
  i = 2
  dict = {
    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
    }
  while i * i <= n:
    while n % i == 0:
      n /= i
      dict[i] = dict[i] + 1
    i += 1
  if n > 1:
    dict[n] = 1
  return dict

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

cum_dict = {
    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
    }
for i in range(N+1):
  decomposed = prime_decomposition(i)
  for p in decomposed.keys():
    cum_dict[p] += decomposed[p]

ans = 0
decomposed_list = list(cum_dict.values())

four_ = sum(x >= 4 for x in decomposed_list)
two_three = sum(2<= x < 4 for x in decomposed_list)
ans += comb(four_,3) * 3
ans += two_three * comb(four_,2)

two_twentythree = sum(2 <= x < 24 for x in decomposed_list)
twentyfour_ = sum(24 <= x for x in decomposed_list)
ans += comb(twentyfour_,2) * 2
ans += two_twentythree * twentyfour_

four_thirteen = sum(4 <= x < 14 for x in decomposed_list)
fourteen_ = sum(14 <= x for x in decomposed_list)
ans += comb(fourteen_,2) * 2
ans += four_thirteen * fourteen_

seventyfour_ = sum(74 <= x for x in decomposed_list)
ans += seventyfour_

print(int(ans))

Submission status: Accepted

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

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


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


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

Submission status: Accepted

Solution code:
N = int(input())
div_num = [0]*(N+1)
for i in range(2,N+1):
    cur = i
    for j in range(2,i+1):
        while cur % j == 0:
            div_num[j] += 1
            cur = cur // j
MAX_VALUE = 80
dp = [0]*(MAX_VALUE)
dp[1] = 1
for i in range(2,N+1):
    for j in range(MAX_VALUE-1,-1,-1):
        for k in range(1,div_num[i]+1):
            next_ = j * (k+1)
            if next_ >= MAX_VALUE:
                break
            dp[next_] += dp[j]
print(dp[75])

Submission status: Accepted

Solution code:
import itertools

primes = [2,3,5,7] + [x for x in range(10,100) if (x%2 and x%3 and x%5 and x%7)]

def fact_ord(p,n):
  return n//p+fact_ord(p,n//p) if n else 0

N = int(input())

order = [fact_ord(p,N) for p in primes]

arr = [0]*80 # 約数の個数ごとにいくつあるか
arr[1] = 1

for e in order:
  temp = [0]*80
  for ee,j in itertools.product(range(e+1),range(80)):
    y = min((ee+1)*j,79)
    temp[y] += arr[j]
  arr = temp
  
answer = arr[75]
print(answer)

Submission status: Accepted

Solution code:
N = int(input())

def factorize(N):
    i = 2
    d = {}
    while i**2 <= N:
        while N%i == 0:
            N /= i
            if i in d.keys():
                d[i] += 1
            else:
                d[i] = 1
        i += 1
    if N > 1:
        d[N] = 1
    return d

c = 0
d = {}
for n in range(1,N+1):
    i = 2
    while i**2 <= n:
        while n%i == 0:
            n /= i
            if i in d.keys():
                d[i] += 1
            else:
                d[i] = 1
        i += 1
    if n > 1:
        if n in d.keys():
            d[n] += 1
        else:
            d[n] = 1

c2 = 0
c4 = 0
c14 = 0
c24 = 0
c74 = 0
for i in d.values():
    if i >= 2:
        c2 += 1
    if i >= 4:
        c4 += 1
    if i >= 14:
        c14 += 1
    if i >= 24:
        c24 += 1
    if i >= 74:
        c74 += 1
ans = c4*(c4-1)/2*(c2-2) + c24*(c2-1) + c14*(c4-1) + c74
print(int(ans))

Submission status: Accepted

Solution code:
N = int(input())


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


e = [0] * (N + 1)
for i in range(1, N + 1):
    for s in factorize(i):
        e[s] += 1


def f(n):
    cnt = 0
    for x in e:
        if x >= n - 1:
            cnt += 1
    return cnt


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

Submission status: Accepted

Solution code:
import math


def primes(x):
    x+=1
    if x < 2:
        return []

    prime = [i for i in range(x)]
    prime[1] = 0

    for p in prime:
        if p > math.sqrt(x):
            break
        if p == 0:
            continue
        for non_prime in range(2 * p, x, p):
            prime[non_prime] = 0

    return [p for p in prime if p != 0]


def over(l, x):
    ans = 0
    for i in range(len(l)):
        if l[i] >= x:
            ans += 1
    return ans


def combinations_count(n, r):
    return math.factorial(n)//(math.factorial(n-r) * math.factorial(r))


n = int(input())


p = primes(n)
r = [1 for i in range(len(p))]

for i in range(n):
    j = 0
    k = i+1
    while k!=1:
        while k%p[j]==0:
            r[j]+=1
            k//=p[j]
        j+=1

ans = 0

ans += over(r,75)

for i in range(len(r)):
    if r[i]>=25:
        ans += over(r,3)-1
    if r[i]>=15:
        ans += over(r,5)-1

o5 = over(r,5)
o3 = over(r,3)
if o5>=2 and o3>=3:
        ans += combinations_count(o5,2) * combinations_count(o3-2,1)

print(ans)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())


def factor(n, f_dict):
    """素因数分解してdictionaryを返す"""
    num = n
    for i in range(2, int(math.sqrt((n)))+1):
        while num % i == 0:
            num = int(num / i)
            fact_dict[i] += 1
        if num == 1:
            return fact_dict
    fact_dict[num] += 1
    return fact_dict


fact_dict = defaultdict(lambda: 0)
for n in range(2, N+1):
    fact_dict = factor(n, fact_dict)


g_2 = []
g_4 = []
g_14 = []
g_24 = []
g_74 = []
for k, v in fact_dict.items():
    if v >= 74:
        g_74.append(k)
    if v >= 24:
        g_24.append(k)
    if v >= 14:
        g_14.append(k)
    if v >= 4:
        g_4.append(k)
    if v >= 2:
        g_2.append(k)

len_2 = len(g_2)
len_4 = len(g_4)
len_14 = len(g_14)
len_24 = len(g_24)
len_74 = len(g_74)

print(len_74+len_24*(len_2-1)+len_14*(len_4-1)+len_4*(len_4-1)//2*(len_2-2))

Submission status: Accepted

Solution code:
n=int(input())
s_dict={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}
for i in range(1,n+1):
    for j in s_dict:
        while i%j==0:
            s_dict[j]=s_dict[j]+1
            i=i//j
count3=0
count5=0
count15=0
count25=0
count75=0
for i in s_dict.values():
    if i>=2:
        count3=count3+1
    if i>=4:
        count5=count5+1
    if i>=14:
        count15=count15+1
    if i>=24:
        count25=count25+1
    if i>=74:
        count75=count75+1
a=count75
b=count25*(count3-count25)+count25*(count25-1)
c=count15*(count5-count15)+count15*(count15-1)
d=(count5*(count5-1)//2)*(count3-count5)+count5*(count5-1)*(count5-2)//2
print(a+b+c+d)

Submission status: Accepted

Solution code:
N = int(input())

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

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

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

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

Submission status: Accepted

Solution code:
N=int(input())
e=[0]*(N+1)
for i in range(2,N+1):
    cur=i
    for j in range(2,i+1):
        while cur%j==0:
            e[j]+=1
            cur//=j

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

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

Submission status: Accepted

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


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


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

C = Counter(T)


def num(x):
    ret = sum([cnt >= x - 1 for cnt in C.values()])
    return ret


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

Submission status: Accepted

Solution code:
N=int(input())

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import math

def combinations(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def p_factors(n):
    if n < 2:
        return defaultdict(int)
    d = 2
    result = defaultdict(int)
    while n > 1 and d*d <= n:
        while n % d == 0:
            result[d] += 1
            n //= d
        d += 1
        
    if n > 1:
        # n is a prime
        result[n] += 1
    return result

N = int(input())
primes = defaultdict(int)
for i in range(2, N+1):
    for p, n in p_factors(i).items():
        primes[p] += n
check = [2, 4, 14, 24, 74]
n_factors_at_least = {i: 0 for i in check}
for _, n in primes.items():
    for i in check:
        if n < i:
            break
        n_factors_at_least[i] += 1
ans = n_factors_at_least[74]
ans += n_factors_at_least[24] * (n_factors_at_least[2]-1) if n_factors_at_least[2] > 1 else 0
ans += n_factors_at_least[14] * (n_factors_at_least[4]-1) if n_factors_at_least[4] > 1 else 0
ans += combinations(n_factors_at_least[4], 2) * (n_factors_at_least[2] - 2) if n_factors_at_least[2] > 2 else 0
print(ans)

Submission status: Accepted

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
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]
DP = [[0 for _ in range(len(prime))] for _ in range(N+1)]
for ind,i in enumerate(DP):
    num = ind
    if(ind == 0):
        continue
    for p_ind,j in enumerate(prime):
        DP[ind][p_ind]=DP[ind-1][p_ind]
        if(j>num or num==1):
            continue
        while(num%j == 0):
            DP[ind][p_ind]+=1
            num//=j
cnt_74 = 0
cnt_24 = 0
cnt_14 = 0
cnt_4 = 0
cnt_2 = 0
cnt_1 = 0
ans = 0
for i in DP[N]:
    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
    if(i>=1):
        cnt_1+=1

ans+=cnt_74
if(cnt_24>=1):
    ans+=cnt_24*(cnt_2-1)
if(cnt_14>=1):
    ans+=cnt_14*(cnt_4-1)
if(cnt_4>=2):
    ans+=combinations_count(cnt_4,2)*(cnt_2-2)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())
def comb(n, k):
    return math.factorial(n) // (math.factorial(n - k) * math.factorial(k))

def era(n):
    lis = [i for i in range(3, n + 1, 2)]
    lis.insert(0, 2)
    for ll in lis:
        lis = [i for i in lis if (i == ll or i % ll != 0)]
    return lis


n = ni()
if n == 1:
    print(0)
    exit()
lis = era(n)
lis2 = [[lis[i], 0] for i in range(len(lis))]
for i in range(1, n + 1):
    for j in lis:
        count = 0
        while(i % j == 0):
            i //= j
            count += 1
        lis2[lis.index(j)][1] += count
c74 = 0
c24 = 0
c14 = 0
c4 = 0
c2 = 0
for i in range(len(lis2)):
    if lis2[i][1] >= 74:
        c74 += 1
    if lis2[i][1] >= 24:
        c24 += 1
    if lis2[i][1] >= 14:
        c14 += 1
    if lis2[i][1] >= 4:
        c4 += 1
    if lis2[i][1] >= 2:
        c2 += 1
ans = 0
ans += comb(c4, 2) * (c2 - 2)
ans += c24 * (c2 - 1)
ans += c14 * (c4 - 1)
ans += c74
print(ans)

Submission status: Accepted

Solution code:
def solve(string):
    n = int(string)
    d = [0] * (n + 1)
    for i in range(2, n + 1):
        t = i
        for j in range(2, i + 1):
            while t % j == 0:
                d[j] += 1
                t //= j

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

    f3, f5 = f(3), f(5)
    return str(f(75) + f(25) * (f3 - 1) + f(15) * (f5 - 1) + f5 * (f5 - 1) // 2 * (f3 - 2))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

Solution code:
def solve(string):
    n = int(string)
    p = []
    c = [True] * 101
    c[0] = c[1] = False
    for i, f in enumerate(c):
        if f:
            p.append(i)
            t = 2
            while i * t <= 100:
                c[i * t] = False
                t += 1
    d = {_p: 0 for _p in p}
    for _p in p:
        t = 1
        while _p**t <= n:
            d[_p] += n // (_p**t)
            t += 1

    def f(n):
        return len(list(filter(lambda x: x >= n - 1, d.values())))

    f3, f5 = f(3), f(5)
    ans = 0
    # x**75
    ans += f(75)
    # x**25y**3
    ans += f(25) * (f3 - 1)
    # x**15y**5
    ans += f(15) * (f5 - 1)
    # x**5y**5z**3
    ans += f5 * (f5 - 1) // 2 * (f3 - 2)
    return str(ans)


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

Solution code:
def solve(string):
    n = int(string)
    p = []
    c = [True] * 101
    c[0] = c[1] = False
    for i, f in enumerate(c):
        if f:
            p.append(i)
            t = 2
            while i * t <= 100:
                c[i * t] = False
                t += 1
    d = {_p: 0 for _p in p}
    for _p in p:
        t = 1
        while _p**t <= n:
            d[_p] += n // (_p**t)
            t += 1
    ans = 0
    # x**75
    for v in d.values():
        if v >= 74:
            ans += 1
    # x**25y**3
    x, y = 0, 0
    for v in d.values():
        if v >= 24:
            x += 1
        if v >= 2:
            y += 1
    ans += x * (y - 1)
    # x**15y**5
    x, y = 0, 0
    for v in d.values():
        if v >= 14:
            x += 1
        if v >= 4:
            y += 1
    ans += x * (y - 1)
    # x**5y**5z**3
    x, y = 0, 0
    for v in d.values():
        if v >= 4:
            x += 1
        if v >= 2:
            y += 1
    ans += x * (x - 1) // 2 * (y - 2)
    return str(ans)


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

Solution code:
from math import factorial
from math import sqrt
from math import ceil
from itertools import permutations
from heapq import *
from collections import defaultdict
from copy import deepcopy
from math import log

N=int(input())
def nCr(n,r):
    if n<r:
        return 0
    a=factorial(n)
    b=factorial(n-r)
    c=factorial(r)
    return a//(b*c)
f=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
a=0
b=0
c=0
d=0
e=0
for F in f:
    s=sum([(N//(F**i)) for i in range(1,7)])
    if s>=74:
        e+=1
    elif s>=24:
        d+=1
    elif s>=14:
        c+=1
    elif s>=4:
        b+=1
    elif s>=2:
        a+=1

print(nCr(b+c+d+e,2)*a+nCr(b+c+d+e,3)*3+(c+d+e)*(max(b+c+d+e-1,0))+(e+d)*(max(0,a+b+c+d+e-1))+e)