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:
import sys
input = sys.stdin.readline


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 modInverse(a, p):
    return pow(a, p - 2, p)
def nCr(n, r, p=10**9+7):
    x = 1
    for i in range(r):
        x = (x * (n - i)) % p
    d = 1
    for i in range(1, r + 1):
        d = (d * i) % p
    return (x * modInverse(d, p)) % p


N = int(input())
import collections
A = []
for i in range(2, N+1):
    A.extend(prime_factorize(i))
P = collections.Counter(A)


def f(n):
    return len([k for k, v in P.items() if v >= n])


def main():
    ans = 0
    ans += f(74)
    ans += f(24) * (f(2)-1)
    ans += f(14) * (f(4)-1)
    ans += nCr(f(4), 2) * (f(2)-2)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())

def check(x):
  i = 2
  res = []
  while i * i <= x:
    while x % i == 0:
      x //= i
      res.append(i)
    i += 1
  if x > 1:
    res.append(x)
  return res
table = [0] * (N + 1)
for i in range(2, N + 1):
  for p in check(i):
    table[p] += 1
  #print(check(i))
t = [0]
#print(table)
for p in table:
  if p > 0: t.append(p)
t.sort()
#print(t)
k = len(t)
#print(k)
res = t[-1] >= 74
for i in range(k - 1):
  for j in range(i + 1, k):
    if t[i] + 1 >= 3 and (t[j] + 1 >= 25):
      res += 1
    if t[i] + 1 >= 5 and (t[j] + 1 >= 15):
      res += 1
    if t[i] + 1 >= 15 and (t[j] + 1 >= 5):
      res += 1
    if t[i] + 1 >= 25 and (t[j] + 1 >= 3):
      res += 1
#print(k, res)
for i in range(k - 2):
  for j in range(i + 1, k - 1):
    for l in range(j + 1, k):
      if (t[i] + 1) >= 3 and (t[j] + 1 >= 5) and (t[l] + 1 >= 5):
        res += 1
      if (t[i] + 1) >= 5 and (t[j] + 1 >= 3) and (t[l] + 1 >= 5):
        res += 1
      if (t[i] + 1) >= 5 and (t[j] + 1 >= 5) and (t[l] + 1 >= 3):
        res += 1
print(int(res))

Submission status: Accepted

Solution code:
import collections
n=int(input())
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
c=collections.Counter()
for i in range(2,n+1):
    c+=collections.Counter(prime_factorize(i))
#print(list(c.values()))
cnt1=0
cnt2=0
cnt3=0
cnt4=0
cnt5=0
cnt6=0
cnt7=0
for a in list(c.values()):
    if a>=4:
        cnt1+=1
    if a>=2:
        cnt2+=1

    if a>=14:
        cnt3+=1
    if a>=4:
        cnt4+=1

    if a>=24:
        cnt5+=1
    if a>=2:
        cnt6+=1

    if a>=74:
        cnt7+=1
print(cnt1*(cnt1-1)*(cnt2-2)//2+cnt3*(cnt4-1)+cnt5*(cnt6-1)+cnt7)

Submission status: Accepted

Solution code:
N = int(input())
M = [0] * (101)

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

for i in range(2, N + 1):
  for m in prime_factorize(i):
    M[m] += 1
#print(M[:N+1])

n3, n5, n15, n25, n75 = 0, 0, 0, 0, 0
for i in range(N+1):
  if M[i] >= 2:  n3  += 1
  if M[i] >= 4:  n5  += 1
  if M[i] >= 14: n15 += 1
  if M[i] >= 24: n25 += 1
  if M[i] >= 74: n75 += 1
#print(n3, n5, n15, n25, n75)   

answer = n75 + n25 * (n3 - 1) + n15 * (n5 - 1) + n5 * (n5 - 1) * (n3 - 2) // 2
print(answer)

Submission status: Accepted

Solution code:
from collections import Counter

from math import floor
from collections import Counter

def factoring(n):
    sup = floor(pow(n,1/2))
    for i in range(2,sup+1):
        while n % i == 0:
            c[i] += 1
            n //= i
    if n != 1:
        c[n] += 1
    return c

N = int(input())
c = Counter()

# 1~Nまで素因数分解して合算を求める
for i in range(1, N + 1):
    factoring(i)

# 素因数の数がvalue以上となるような素因数の数
t = Counter()
for _, values in c.items():
    if values >= 2:
        t[2] += 1
    if values >= 4:
        t[4] += 1
    if values >= 14:
        t[14] += 1
    if values >= 24:
        t[24] += 1
    if values >= 74:
        t[74] += 1

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

Submission status: Accepted

Solution code:
l =    [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 = 0
l3, l5, l15, l25, l75 = 0, 0, 0, 0, 0
n = int(input())
for i in l:
  temp = n
  c = 1
  while temp >= i:
    temp //= i
    c += temp
  if c >= 3:
    l3 += 1
  if c >= 5:
    l5 += 1
  if c >= 15:
    l15 += 1
  if c >= 25:
    l25 += 1
  if c >= 75:
    l75 += 1
ans += l75
ans += l25 * (l3-1)
ans += l15 * (l5-1)
ans += (l3-2) * l5*(l5-1) // 2
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    # 終点はルート切り捨て+1
    for i in range(2, int(sqrt(num))+1):
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで分解したら終了
        if num == 1:
            break
    # 最後に残ったnumは素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

N = INT()

# N!までを全部素数冪でまとめる
primes = Counter()
for i in range(2, N+1):
    primes.update(factorize(i))

# 約数が75になる素数冪の組み合わせを数える
primes = sorted(primes.values())
M = len(primes)
cnt = 0
for i, v1 in enumerate(primes):
    # 1種類使う
    if v1 >= 74:
        cnt += 1
    for j, v2 in enumerate(primes[i+1:], i+1):
        # 2種類使う
        if v1 >= 2 and v2 >= 24:
            cnt += 1
        if v1 >= 4 and v2 >= 14:
            cnt += 1
        if v1 >= 24 and v2 >= 2:
            cnt += 1
        if v1 >= 14 and v2 >= 4:
            cnt += 1
        for k, v3 in enumerate(primes[j+1:], j+1):
            # 3種類使う
            if v1 >= 2 and v2 >= 4 and v3 >= 4:
                cnt += 1
            if v1 >= 4 and v2 >= 2 and v3 >= 4:
                cnt += 1
            if v1 >= 4 and v2 >= 4 and v3 >= 2:
                cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table
N=int(input())
_, table = sieve(N)
d={}
for p in table:
    sum_=0
    calc=p
    while calc <= N:
        sum_ += N//calc
        calc *= p
    d[p] = sum_ + 1
def count(d,n):
    return len([i for i in d.values() if i >=n])
print((count(d,3) - 1)*count(d,25) + (count(d,5) - 1)*count(d,15) + count(d,5) * (count(d,5) - 1) * (count(d,3)-2)//2 + count(d,75))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    # 終点はルート切り捨て+1
    for i in range(2, int(sqrt(num))+1):
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで分解したら終了
        if num == 1:
            break
    # 最後に残ったnumは素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

N = INT()

# N!までを全部素数冪でまとめる
primes = Counter()
for i in range(2, N+1):
    primes.update(factorize(i))

# 約数が75になる素数冪の組み合わせを数える
primes = sorted(primes.values())
M = len(primes)
cnt2 = cnt4 = cnt14 = cnt24 = cnt74 = 0
for a in primes:
    # 組み合わせに使える数を予め数えておく
    if a >= 2: cnt2 += 1
    if a >= 4: cnt4 += 1
    if a >= 14: cnt14 += 1
    if a >= 24: cnt24 += 1
    if a >= 74: cnt74 += 1

ans = 0
# 3種類使う
ans += (cnt2-2) * (cnt4 * (cnt4-1) // 2)
# 2種類使う
ans += (cnt2-1) * cnt24 + (cnt4-1) * cnt14
# 1種類使う
ans += cnt74

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    # 終点はルート切り捨て+1
    for i in range(2, int(sqrt(num))+1):
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで分解したら終了
        if num == 1:
            break
    # 最後に残ったnumは素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

N = INT()

# N!までを全部素数冪でまとめる
primes = Counter()
for i in range(2, N+1):
    primes.update(factorize(i))

# 約数が75になる素数冪の組み合わせを数える
primes = sorted(primes.values())
M = len(primes)
cnt = 0
# 3種類使う
for i, v1 in enumerate(primes):
    for j, v2 in enumerate(primes[i+1:], i+1):
        for k, v3 in enumerate(primes[j+1:], j+1):
            if v1 >= 2 and v2 >= 4 and v3 >= 4:
                cnt += 1
            if v1 >= 4 and v2 >= 2 and v3 >= 4:
                cnt += 1
            if v1 >= 4 and v2 >= 4 and v3 >= 2:
                cnt += 1
# 2種類使う
for i, v1 in enumerate(primes):
    for j, v2 in enumerate(primes[i+1:], i+1):
        if v1 >= 2 and v2 >= 24:
            cnt += 1
        if v1 >= 4 and v2 >= 14:
            cnt += 1
        if v1 >= 24 and v2 >= 2:
            cnt += 1
        if v1 >= 14 and v2 >= 4:
            cnt += 1
# 1種類使う
for i, v1 in enumerate(primes):
    if v1 >= 74:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    # 75 * 1
    # 25 * 3
    # 15 * 5
    # 5 * 5 * 3
    N = int(input())
    d = defaultdict(int)
    for n in range(1, N+1):
        for i in range(2, int(n ** 0.5) + 1):
            while n % i == 0:
                d[i] += 1
                n = n // i
        if n != 1:
            d[n] += 1

    d2 = 0
    d4 = 0
    d14 = 0
    d24 = 0
    d74 = 0
    for i in d.values():
        if i >= 2:
            d2 += 1
        if i >= 4:
            d4 += 1
        if i >= 14:
            d14 += 1
        if i >= 24:
            d24 += 1
        if i >= 74:
            d74 += 1

    ans = d74
    ans += d24 * (d2 - 1)
    ans += d14 * (d4 - 1)
    ans += (d4 * (d4 - 1) * (d2 - 2)) // 2

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC 114 D - 756
from collections import defaultdict
def factorize(n):
    """
    引数の値を素因数分解したリストを返す

    Parameters
    ----------
    n : int
        素因数分解したい自然数

    Returns
    -------
    retlist : list
        素因数分解後の値のリスト
    """
    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())
div=[]
for i in range(1,n+1):
    t=factorize(i)
    div+=t

d = defaultdict(int)
for dd in div:
    d[dd]+=1

fact_3=0
fact_5=0
fact_15=0
fact_25=0
fact_75=0

for ddd in d.values():
    if 2<=ddd<4:
        fact_3+=1
    elif 4<=ddd<14:
        fact_5+=1
    elif 14<=ddd<24:
        fact_15+=1
    elif 24<=ddd<74:
        fact_25+=1
    elif 74<=ddd:
        fact_75+=1

fact_3 = fact_75+fact_25+fact_15+fact_5+fact_3
fact_5 = fact_75+fact_25+fact_15+fact_5
fact_15 = fact_75+fact_25+fact_15
fact_25 = fact_75+fact_25
fact_75 = fact_75

ans = 0
ans += (fact_5*(fact_5-1)*(fact_3-2))//2
ans += fact_15*(fact_5-1)
ans += fact_25*(fact_3-1)
ans += fact_75

print(ans)

Submission status: Accepted

Solution code:
def pff(m):
    pf = {}
    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
    return pf
def examD():
    N = I()
    d = defaultdict(int)
    for i in range(2,N+1):
        cur  = pff(i)
        for key,j in cur.items():
            d[key] +=j
#    print(d)
    Num = defaultdict(int)
    for i in d.values():
        for j in [3,5,15,25,75]:
            if i>=j-1:
                Num[j] +=1
            else:
                break
#    print(Num)
    ans = 0
    ans += (Num[5]*(Num[5]-1)//2)*(Num[3]-2)
    ans += Num[15]*(Num[5]-1)
    ans += Num[25]*(Num[3]-1)
    ans += Num[75]
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examD()

Submission status: Accepted

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

Submission status: Accepted

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

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


decomp_dic = defaultdict(int)

for n in range(2, N + 1):
    c = Counter(prime_factorize(n))
    for key, value in c.items():
        decomp_dic[key] += value

for key in decomp_dic.keys():
    decomp_dic[key] += 1

ans = 0
above_25 = 0
above_15 = 0
above_5 = 0
above_3 = 0
for value in decomp_dic.values():
    if value >= 75:
        ans += 1
    if value >= 25:
        above_25 += 1
    if value >= 15:
        above_15 += 1
    if value >= 5:
        above_5 += 1
    if value >= 3:
        above_3 += 1

ans += above_25 * (above_3 - 1)
ans += above_15 * (above_5 - 1)

ans += (above_3 - 2) * above_5 * (above_5 - 1) // 2

print(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]

import math
NK=math.factorial(N)
from itertools import permutations, combinations,combinations_with_replacement,product
L = combinations(range(0,len(primes)), 3)   #nCr
L = list(L)
ans = 0
for i in L:
  x = ((primes[i[0]]**4)*(primes[i[1]]**4)*(primes[i[2]]**2))
  if NK % x ==0:
    ans +=1
  x = ((primes[i[1]]**4)*(primes[i[2]]**4)*(primes[i[0]]**2))
  if NK % x ==0:
    ans +=1
  x = ((primes[i[2]]**4)*(primes[i[0]]**4)*(primes[i[1]]**2))
  if NK % x ==0:
    ans +=1

L = combinations(range(0,len(primes)), 2)   #nCr
L = list(L)
for i in L:
  x = ((primes[i[0]]**24)*(primes[i[1]]**2))
  if NK % x ==0:
    ans +=1
  x = ((primes[i[1]]**24)*(primes[i[0]]**2))
  if NK % x ==0:
    ans +=1
  x = ((primes[i[0]]**14)*(primes[i[1]]**4))
  if NK % x ==0:
    ans +=1
  x = ((primes[i[1]]**14)*(primes[i[0]]**4))
  if NK % x ==0:
    ans +=1

L = combinations(range(0,len(primes)), 1)   #nCr
L = list(L)
for i in L:
  x = ((primes[i[0]]**74))
  if NK % x ==0:
    ans +=1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def searchPrimeNum(N):
    max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

plis = searchPrimeNum(100)

def pfact(N,dic):
    for p in plis:
        if N%p == 0:
            dic[p] += 1
            N = N//p
        while N%p == 0:
            dic[p] += 1
            N = N//p
        if N == 1:
            break
    return dic

dict = {}
for p in plis:
    dict[p] = 0

for i in range(1,N+1):
    dict = pfact(i,dict)

nlis = [0,0,0,0,0]
r = [75,25,15,5,3]
for i in dict.values():
    for j in range(len(r)):
        if i >= r[j]-1:
            nlis[j] += 1
ans = 0
ans += nlis[0]
ans += nlis[1]*(nlis[-1]-1)
ans += nlis[2]*(nlis[-2]-1)
ans += nlis[-2]*(nlis[-2]-1)*(nlis[-1]-2)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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]
ans = 0
factor = defaultdict(int)
for i in range(1,N+1):
    for j in prime:
        while i != 1:
            if i % j == 0:
                factor[j] += 1
                i = i // j
            else:
                break

fact_l = list(dict(factor).items())
fact_l.sort()
n_74 = 0
n_24 = 0
n_14 = 0
n_4 = 0
n_2 = 0
for i, x in enumerate(fact_l):
    if x[1] >= 74:
        n_74 = i + 1
    if x[1] >= 24:
        n_24 = i + 1
    if x[1] >= 14:
        n_14 = i + 1
    if x[1] >= 4:
        n_4 = i + 1
    if x[1] >= 2:
        n_2 = i + 1

print(n_74+(n_24*(n_2-1))+(n_14*(n_4-1))+(n_4*(n_4-1)*(n_2-2)//2))

Submission status: Accepted

Solution code:
N = int(input())

primenum = [0]*101

def make_divisor(n):
    res = []
    for i in range(1,int(n**0.5+1)):
        if i*i == n:
            res.append(i)
        else:
            res.append(i)
            res.append(n//i)
    return res

def fact(n):
    if n==1:
        return 
    else:
        divs = make_divisor(n)
        divs.sort()
        tmp = n
        idx = 1
        while(tmp>1):
            while (tmp%divs[idx]==0):
                primenum[divs[idx]] += 1
                tmp //= divs[idx]
            idx += 1
        fact(n-1)
        return 


fact(N)

ans = 0
primenum.sort(reverse = True)
idx = 0
while primenum[idx]>=74: idx += 1
ans += idx

idx2 = 0
while primenum[idx]>=24: idx += 1
while primenum[idx+idx2]>=2:idx2 += 1
ans += idx*(idx-1+idx2)

idx = 0
idx2 = 0
while primenum[idx]>=14: idx += 1
while primenum[idx+idx2]>=4:idx2 += 1
ans += idx*(idx-1+idx2)

idx = idx+idx2
idx2 = 0
while primenum[idx+idx2]>=2: idx2 += 1
ans += idx*(idx-1)//2*(idx-2+idx2)
print(ans)

Submission status: Accepted

Solution code:
import collections

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

N = int(input())
Prime=[]
for i in range(2,N+1):
  Prime +=prime_factorize(i)
  
c=collections.Counter(Prime)
P_count=c.values()

count_2=len([1 for x in P_count if x>=2])
count_4=len([1 for x in P_count if x>=4])
count_14=len([1 for x in P_count if x>=14])
count_24=len([1 for x in P_count if x>=24])
count_74=len([1 for x in P_count if x>=74])
answer=(count_2-2)*(count_4-1)*count_4//2+(count_4-1)*count_14+(count_2-1)*count_24+count_74
print(answer)

Submission status: Accepted

Solution code:
N = int(input())
import math
import random
from itertools import permutations

res_dict = {i : 0 for i in range(1,101)}
class Prime:
    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]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

        :param n:
        :return: boolean
        """
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed+1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes


prime = Prime()
for i in range(2,N+1):
    res = prime.find_factors(i)
    for k, v in res.items():
        res_dict[k] += v
res_dict = {i : j + 1 for i, j in res_dict.items() if j >= 2}
res = 0
for combi in permutations(res_dict.items(), 3):
    if combi[0][1] >= 5 and combi[1][1] >= 5:
        res += 1
res //= 2
for combi in permutations(res_dict.items(), 2):
    if combi[0][1] >= 25:
        res += 1
    if combi[0][1] >= 15 and combi[1][1] >= 5:
        res += 1
for combi in res_dict.items():
    if combi[1] >= 75:
        res += 1
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math

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

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

def solve(N: int):
    from collections import Counter
    counter = Counter(prime_decomposition(math.factorial(N)))
    prime_counts = sorted(list(counter.values()),reverse=True)

    ## key個以上あるもののindex
    d = {74:[],24:[],14:[],4:[],2:[],1:[]}
    for i,count in enumerate(prime_counts):
        for key,_ in d.items():
            if count>=key:
                d[key].append(i)

    answer = 0
    ## ○**74の形のものが何個作れるか
    if d.get(74):
        answer += len(d[74])
    ## ○**24○*2の形のものが何個作れるか
    if d.get(24):
        answer += len(d[24])*(len(d[2])-1)

    ## ○**14○*4の形のものが何個作れるか
    if d.get(14):
        answer += len(d[14])*(len(d[4])-1)

    if len(d.get(4))>=2:
        answer += combinations_count(len(d[4]),2)*(len(d[2])-2)

    print(answer)
    return


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

if __name__ == '__main__':
    main()

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 defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    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] = 0
    return {i for i in range(n + 1) if is_prime[i]}


n = I()
prime_set = primes(n)
prime_cnt = Counter()
for p in prime_set:
    pi = p
    while pi < n:
        prime_cnt[p] += n // pi
        pi *= p


prime_cnt = [v for k, v in prime_cnt.most_common()][::-1]
m = len(prime_cnt)
print(m - bisect_left(prime_cnt, 74) + (m - bisect_left(prime_cnt, 24)) * (m - bisect_left(prime_cnt, 2) - 1)
    + (m - bisect_left(prime_cnt, 14)) * (m - bisect_left(prime_cnt, 4) - 1)
    + (m - bisect_left(prime_cnt, 4)) * ((m - bisect_left(prime_cnt, 4)) - 1) // 2 * ((m - bisect_left(prime_cnt, 2)) - 2))

Submission status: Accepted

Solution code:
A=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

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 

B=[0]*15
for i in range(1,int(input())+1):
    w=prime_factorize(i)
    for j in w:
        if j<=47:
            B[A.index(j)]+=1

def num(m):
    return len(list(filter(lambda x:x>=m,B)))

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