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 primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

N = int(input())

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

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

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

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from collections import defaultdict
import itertools

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

def prime_factorize(n): # Nの素因数分解
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

# 約数の組み合わせ（３・５・５）（７５）など
N = ir()
dic = defaultdict(int)
for x in range(2, N+1):
    primes = prime_factorize(x)
    for p in primes:
        if p in dic:
            dic[p] += 1
        else:
            dic[p] = 1

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

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

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

print(answer)
# 40

Submission status: Accepted

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

result = 0

result += end

result += tw*(t-1)

result += ft*(f-1)

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

print(result)

Submission status: Accepted

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

# nを素因数分解したリストを返す
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table

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

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

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

m = len(li)

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

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

ans2 = 0

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

ans += ans2 // 2

print(ans)

Submission status: Accepted

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

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

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

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

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

"""素因数分解"""
def factrize(n):
    b = 2
    fct = []
    while b*b <= n:
        while n % b == 0:
            n //= b
            #もし素因数を重複させたくないならここを加えてfct.append(b)を消す
            """
            if not b in fct:
                fct.append(b)
            """
            fct.append(b)
        b = b+1
    if n > 1:
        fct.append(n)
    return fct #リストが帰る

#二項係数(modなし) O(k)
def large_conbination(n,k): #no mod. return nCk.
    res1 = 1
    for i in range(n,n-k,-1):
        res1*=i
    res2 = 1
    for i in range(1,k+1):
        res2*= i
    return res1//res2

for i in range(2,n+1): #n!を素因数分解する時、各要素ごとに素因数分解しても結果は変わらない
    for j in factrize(i):
        dic1[j] += 1

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

#解法の条件を満たす通り数の順に再現
print(
    large_conbination(num(5),2)*(num(3)-2) +
    num(15)*(num(5)-1) + 
    num(25)*(num(3)-1) +
    num(75)
)

Submission status: Accepted

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

def main():
    n = ni()

    e = [0] * (n + 1)

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

    for i in range(2, n+1):
        cur = i
        for j in range(2, i+1):
            while cur % j == 0:
                e[j] += 1
                cur //= j
    
    print(num(75) + num(25)*(num(3) - 1) + num(15)*(num(5) - 1)
        + num(5)*(num(5) - 1)*(num(3) - 2) // 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
#75=5*5*3=25*3=15*5=75*1
#100!=9.3*10^157
#2^74=1.8*10^12,3^74=...,140^74=
#つまり,4こ-4こ-2こ、24こ-2こ、14こ-4こ,74こ
#となる組み合わせの探査になる?
insuu=[0]*(100+1)
l=[]
sevenfour=0
twofour=0
onefour=0
four=0
two=0
for k in range(N):
    pf = {}
    m = k+1
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1: pf[m] = 1
    #print(pf)
    keys = list(pf.keys())
    values = list(pf.values())
    for i in range(len(keys)):
        insuu[keys[i]]=insuu[keys[i]]+values[i]
    # print(l)	#これでlistになった
#print(insuu)
for i in range(101):
    if insuu[i]>=74:
        sevenfour = sevenfour+1
    if insuu[i]>=14:
        onefour=onefour+1
    if insuu[i]>=24:
        twofour=twofour+1
    if insuu[i]>=4:
        four=four+1
    if insuu[i]>=2:
        two=two+1
print(((four*(four-1))//2)*(two-2)+twofour*(two-1)+onefour*(four-1)+sevenfour)

Submission status: Accepted

Solution code:
def factorization(n):
    ans = {}
    i = 2
    while n > 1:
        count = 0
        while n % i == 0:
            n = n // i
            count += 1
        if count != 0:
            ans[i] = count
        i += 1
    return ans


N = int(input())
primes = {}
for n in range(2, N + 1):
    factors = factorization(n)
    for f in factors:
        if f in primes:
            primes[f] += factors[f]
        else:
            primes[f] = factors[f]

ans = 0
# 75
for p in primes:
    if primes[p] >= 74:
        ans += 1

# 25 * 3 and 15 * 5
for p in primes:
    for q in primes:
        if p == q:
            continue
        if primes[p] >= 24 and primes[q] >= 2:
            ans += 1
        if primes[p] >= 14 and primes[q] >= 4:
            ans += 1

# 3 5 5
for p in primes:
    if primes[p] >= 2:
        for q in primes:
            if p != q and primes[q] >= 4:
                for r in primes:
                    if p != r and q != r and primes[r] >= 4 and q < r:
                        ans += 1
print(ans)

Submission status: Accepted

Solution code:
data = int(input())
e = [0] * (data+1)
for i in range(2, data+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:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def pm(X):
    res = {}
    for i in range(2, int(X ** 0.5) + 1):
        if X % i == 0:
            res[i] = 0
            while X % i == 0:
                X //= i
                res[i] += 1
    if X > 1:
        res[X] = 1
    return res


def solve():
    N = Scanner.int()

    # N!の素因数分解
    M = defaultdict(int)
    for i in range(2, N + 1):
        tmp = i
        for j in range(2, int(i ** 0.5) + 1):
            while tmp % j == 0:
                M[j] += 1
                tmp //= j
        if tmp > 1:
            M[tmp] += 1

    ans = 0

    # 75
    for p in range(2, N+1):
        if M[p] >= 74:
            ans += 1

    # 3 * 25
    # 5 * 25
    for p in range(2, N + 1):
        for q in range(2, N+1):
            if p == q:
                continue
            if M[p] >= 2 and M[q] >= 24:
                ans += 1
            if M[p] >= 4 and M[q] >= 14:
                ans += 1

    # 5 * 5 * 3
    for p in range(2, N+1):
        for q in range(p + 1, N + 1):
            for r in range(2, N + 1):
                if p == r:
                    continue
                if q == r:
                    continue
                if M[p] >= 4 and M[q] >= 4 and M[r] >= 2:
                    ans += 1
    print(ans)


def main():
    # sys.stdin = open("sample.txt")
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def pm(X):
    res = {}
    for i in range(2, int(X ** 0.5) + 1):
        if X % i == 0:
            res[i] = 0
            while X % i == 0:
                X //= i
                res[i] += 1
    if X > 1:
        res[X] = 1
    return res


def solve():
    N = Scanner.int()
    M = defaultdict(int)
    for i in range(2, N + 1):
        d = pm(i)
        for k, v in d.items():
            M[k] += v

    ans = 0
    for r in range(2, N + 1):
        for p in range(2, N+1):
            for q in range(p + 1, N + 1):
                if p == r:
                    continue
                if q == r:
                    continue
                if M[r] >= 2 and M[p] >= 4 and M[q] >= 4:
                    ans += 1

    for p in range(2, N + 1):
        if M[p] >= 74:
            ans += 1

    for p in range(2, N + 1):
        for q in range(2, N+1):
            if p == q:
                continue
            if M[p] >= 14 and M[q] >= 4:
                ans += 1
            if M[p] >= 24 and M[q] >= 2:
                ans += 1
    print(ans)


def main():
    # sys.stdin = open("sample.txt")
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

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

def DictAppend(n,d):
    if n in d:
        d[n]+=1
    else:
        d[n]=1

for i in range(1,n+1):
    if i==1:
        continue
    now=i
    while now%2==0:
        now//=2
        DictAppend(2,D)
    p=3
    while p<=math.sqrt(i):
        while now%p==0:
            now//=p
            DictAppend(p,D)
        p+=2
        if now==1:
            break
    if now>math.sqrt(i):
        DictAppend(now,D)

P=[74,24,14,4,2]
C=[0,0,0,0,0]
for d in D:
    for i in range(5):
        if D[d]>=P[i]:
            C[i]+=1

ans=0
ans+=C[0] #a**74
if C[4]>1:
    ans+=C[1]*(C[4]-1) #a**24 * b**2
if C[3]>1:
    ans+=C[2]*(C[3]-1) #a**14 * b**4
if C[4]>2:
    ans+=C[3]*(C[3]-1)//2*(C[4]-2) #a**4 * b**4 * c**2
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

# n!の素因数分解での素数pの指数
e = [0] * (n + 1)
for i in range(2, n + 1):
	tmp = i
	for j in range(2, i + 1):
		while tmp % j == 0:
			e[j] += 1
			tmp //= j

# e の要素のうち m-1 以上のものの個数
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:
import sys
import math

input = sys.stdin.readline


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


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

    ef = [0] * (N + 1)
    ans = 0
    for i in range(2, N + 1):
        x = prime_factorization(i)
        for xx in x:
            ef[xx] += 1

    a, b, c, d, e = 0, 0, 0, 0, 0
    for ee in ef:
        if ee >= 74:
            a += 1
            b += 1
            c += 1
            d += 1
            e += 1
        elif ee >= 24:
            a += 1
            b += 1
            c += 1
            d += 1
        elif ee >= 14:
            a += 1
            b += 1
            c += 1
        elif ee >= 4:
            a += 1
            b += 1
        elif ee >= 2:
            a += 1

    ans += e
    ans += d * (a - 1)
    ans += c * (b - 1)
    ans += b * (b - 1) * (a - 2) // 2

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce

def comb(n, r):
    if n < 0 or r < 0 or r > n:
        return 0
    r = min(r, n - r)
    if r == 0: return 1

    numer = [n - r + i + 1 for i in range(r)]
    denom = [i + 1 for i in range(r)]

    for i in range(1, r):
        divisor = denom[i]
        if divisor > 1:
            offset = (n - r) % (i + 1)
            for j in range(i, r, i+1):
                numer[j - offset] //= divisor
                denom[j] //= divisor

    return reduce(lambda x, y: x*y if y > 1 else x, numer)

def sieve(n):
    a = [1] * (n + 1)
    a[0] = a[1] = False
    for i in range(4, n+1, 2):
        a[i] = False
    lim = int(n**0.5) + 1
    for i in range(3, lim + 1, 2):
        if a[i]:
            for j in range(i + i, n + 1, i):
                a[j] = False
    return a

N = int(input())

factors = []
sv = sieve(N)
for p in range(2, N+1):
    if sv[p]:
        n = N
        x = 0
        while n // p > 0:
            n //= p
            x += n
        if x > 0:
            factors.append([p, x])

# print(factors)
ans = 0
for xx in [[[4,2],[2,1]],[[14,1],[4,1]],[[24,1],[2,1]],[[74,1]]]:
    c = 1
    done = 0
    for i, x in enumerate(xx):
        s = sum(f[1] >= x[0] for f in factors)
        s = max(0, s - done)
        if s < x[1]:
            c = 0
            break
        else:
            c *= comb(s, x[1])
            done += x[1]
    ans += c

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import Counter
from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


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


n = int(readline())
table = []
for i in range(1, n + 1):
    table += prime_decomposition(i)
counter = list(Counter(table).values())
ans = [0, 0, 0, 0, 0]
for v in counter:
    if v >= 2:
        ans[0] += 1
        if v >= 4:
            ans[1] += 1
            if v >= 14:
                ans[2] += 1
                if v >= 24:
                    ans[3] += 1
                    if v >= 74:
                        ans[4] += 1
if n < 10:
    print(0)
    exit()
print(ans[4] + ans[3] * (ans[0] - 1) + ans[2] * (ans[1] - 1) + (ans[0] - 2) * cmb(ans[1], 2))

Submission status: Accepted

Solution code:
import math

def decompose(d, n):
    limit = (int)(math.sqrt(n)) + 1
    for i in range(2, limit):
        while n % i == 0:
            if i not in d:
                d[i] = 0
            d[i] += 1
            n //= i
    if n != 1:
        if n not in d:
            d[n] = 0
        d[n] += 1

def main():
    N = int(input())
    D = {}
    for i in range(2, N + 1):
        decompose(D, i)
    f2, f4, f14, f24, f74 = 0, 0, 0, 0, 0
    for d in D:
        n = D[d]
        if n >= 74:
            f74 += 1
        if n >= 24:
            f24 += 1
        if n >= 14:
            f14 += 1
        if n >= 4:
            f4 += 1
        if n >= 2:
            f2 += 1
    # print(D, f2, f4, f14, f24, f74)
    if f2 == 0 or f4 < 2:
        print(0)
        return
    # 75
    ans = f74
    # 25 * 3
    ans += f24 * (f2 - 1)
    # 15 * 5
    ans += f14 * (f4 - 1)
    # 5 * 5 * 3
    ans += f4 * (f4 - 1) // 2 * (f2 - 2)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

n=int(input())

def soinsu(n):
    S = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            S.append(i)
    if S == []:
        S.append(n)
    else:
        if n != 1:
            S.append(n)
    return S
L=[]
if n >= 2:
    for i in range(2, n + 1):
        L = L + soinsu(i)
LC = Counter(L)

C2 = 0
C4 = 0
C14 = 0
C24 = 0
C74 = 0

for v in LC.values():
    if v >= 2:
        C2 += 1
        if v >= 4:
            C4 += 1
            if v >= 14:
                C14 += 1
                if v >= 24:
                    C24 += 1
                    if v >= 74:
                        C74 += 1

r = C4 * (C4 - 1) // 2 * (C2 - 2) + C14 * (C4 - 1) + C24 * (C2 - 1) + C74

print(r)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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(n):
    return len(list(filter(lambda x: x >= n-1, e)))

# num(3)-1はnum(25)で3以上のものを一個使っているので、一つ引いている。//2は、例えばa^4 * b^4 * c^2 と b^4 * a^4 * c^2がかぶって計上されるため。
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())
def is_p(k):
  for i in range(2,int(k**0.5)+1):
    if k%i == 0:
      return False
  return True
p = []
for i in range(2,n+1):
  if is_p(i):
    p.append(i)
l = len(p)
q =[0]*l
for i in range(2,n+1):
  for j in range(l):
    if i == 1:
      break
    while i%p[j] == 0:
      q[j] += 1
      i /= p[j]
c = 0
for qi in q:
  if qi >= 74:
    c += 1
o2 = 0
o4 = 0
o14 = 0
o24 = 0
for qi in q:
  if qi >= 24:
    o24 += 1
  elif qi >= 14:
    o14 += 1
  elif qi >= 4:
    o4 += 1
  elif qi >= 2:
    o2 += 1
c += o24*(o2+o4+o14+o24-1)
c += (o14+o24)*(o4+o14+o24-1)
c += (o2+o4+o14+o24-2)*(o4+o14+o24)*(o4+o14+o24-1)//2  
print(c)

Submission status: Accepted

Solution code:

import math


def prime_factorization(x):
    if x == 1:
        return {1: 1}

    notprime = {}
    pf = {}
    for y in range(2, math.ceil(math.sqrt(x)) + 1):
        if y not in notprime.keys():
            if x % y == 0:
                pf[y] = 0
                while x % y == 0:
                    x //= y
                    pf[y] += 1
            
            coef = 2
            while coef * y < x:
                notprime[coef * y] = True
                coef += 1
    if x > 1:
        pf[x] = 1    
    return pf


def submit():
    n = int(input())

    #　階乗の素因数分解を求める
    pf_all = {}
    for x in range(2, n + 1):
        pf = prime_factorization(x)
        for k, v in pf.items():
            if k not in pf_all.keys():
                pf_all[k] = v
            else:
                pf_all[k] += v

    pf_cand = [v for k, v in pf_all.items() if v > 1]
    pf_cand.sort()
    possible_divisors = [1, 3, 5, 15, 25, 75]
    
    def dfs(curr, rest, cnt):
        if curr > 75:
            return cnt
        if not rest:
            if curr == 75:
                return cnt + 1
            else:
                return cnt
        
        l = rest[-1]
        new_rest = rest[:-1]
        for p in possible_divisors:
            if p - 1 <= l:
                cnt = dfs(curr * p, new_rest, cnt)
            else:
                break
        return cnt
            
    print(dfs(1, pf_cand, 0))


if __name__ == "__main__":
    submit()

Submission status: Accepted

Solution code:
n = int(input())
p = (n+1)*[0]

for i in range(2, n+1):
    now = i
    for j in range(2, i+1):
        while now % j == 0:
            p[j] += 1
            now //= j


def cnt(m):
    return len(list(filter(lambda x: x >= m, p)))


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

Submission status: Accepted

Solution code:
from math import sqrt, ceil
from collections import defaultdict
def prime(N):
    temp = [True]*(N+1)
    temp[0] = temp[1] = False
    for i in range(2, ceil(sqrt(N+1))):
        if temp[i]:
            temp[i+i::i] = [False]*(len(temp[i+i::i]))                            
    primes = [ n for n in range(N+1) if temp[n] ]
    return primes
n = int(input())
dic = defaultdict(lambda:0)
p = prime(n)
for i in range(1,n+1):
    for j in p:
        while i % j == 0:
            i //= j
            dic[j] += 1
        if i == 1:
            break
a = 0 #75
b = 0 #25
c = 0 #15
d = 0 #5
e = 0 #3
for i in dic.keys():
    if dic[i] >= 74:
        a += 1
    if dic[i] >= 24:
        b += 1
    if dic[i] >= 14:
        c += 1
    if dic[i] >= 4:
        d += 1
    if dic[i] >= 2:
        e += 1
ans = 0
ans += a
ans += b*(e-1)
ans += c*(d-1)
ans += d*(d-1)*(e-2)//2
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
P = [1]*(N+1)
for i in range(1,N+1):
    n = i
    for j in range(2,N+1):
        while n%j==0:
            P[j]+=1
            n//=j
P = [p for p in P if p>1]
N = len(P)-1
cnt = 0
B = [1,3,5,15,25,75]
def f(k,d):
    global N,P,cnt,B
    if d==75:
        cnt += 1
        return
    elif d>75 or k>N:
        return
    for i in range(1,P[k]+1):
        if i in B:
            f(k+1,d*i)
f(0,1)
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
ans = 0

prime = [1]*100
prime = np.array(prime)
for i in range(2,n+1):
    temp = 1
    for j in range(2,100):
        while i%j == 0:
            i //= j
            prime[j] += 1
    # print(i,prime)
p75 = prime//75
p25 = prime//25
p15 = prime//15
p5 = prime//5
p3 = prime//3
for i in range(100):
    if p75[i] >= 1:
        ans += 1
    if p25[i] >= 1:
        for j in range(i+1,100):
            if p3[j] >= 1:
                ans += 1
                # print(i,j)
    if p15[i] >= 1:
        for j in range(i+1,100):
            if p5[j] >= 1:
                ans += 1
    if p5[i] >= 1:
        for j in range(i+1,100):
            if p15[j] >= 1:
                ans += 1
            if p5[j] >= 1:
                for k in range(j+1,100):
                    if p3[k] >= 1:
                        ans += 1
                        # print(i,j,k)
            if p3[j] >= 1:
                for k in range(j+1,100):
                    if p5[k] >= 1:
                        ans += 1 
    if p3[i] >= 1:
        for j in range(i+1,100):
            if p25[j] >= 1:
                ans += 1
            if p5[j] >= 1:
                for k in range(j+1,100):
                    if p5[k] >= 1:
                        ans += 1 
# print(prime)
# print(p5)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

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

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())
pl=[2]
for i in range(3,N+1):
  if all(i%p!=0 for p in pl):
    pl.append(i)
pd={}
Nf=math.factorial(N)
for i in range(len(pl)):
  if Nf%pl[i]==0:
    pd[pl[i]]=1
    Nf//=pl[i]
    while Nf%pl[i]==0:
      pd[pl[i]]+=1
      Nf//=pl[i]
l74=[]
l24=[]
l14=[]
l4=[]
l2=[]
for i in range(len(pd)):
  if pd[pl[i]]>=74:
    l74.append(pl[i])
  if pd[pl[i]]>=24:
    l24.append(pl[i])
  if pd[pl[i]]>=14:
    l14.append(pl[i])
  if pd[pl[i]]>=4:
    l4.append(pl[i])
  if pd[pl[i]]>=2:
    l2.append(pl[i])
ans1=len(l74)
ans2=len(l24)*(len(l2)-1) if len(l2)>=1 else 0
ans3=len(l14)*(len(l4)-1) if len(l4)>=1 else 0
ans4=(len(l4)-1)*len(l4)*(len(l2)-2)//2 if len(l2)>=2 else 0
print(ans1+ans2+ans3+ans4)

Submission status: Accepted

Solution code:
n = int(input())
e = [0 for _ in range(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)))

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    #[i]:数字iの個数
    prime_list = [0]*100
    # 素因数分解
    def prime_decomp(n):
        i = 2
        res = []
        while i ** 2 <= n:
            while n % i==0:
                n //= i
                res.append(i)
            i += 1
        if n > 1:
            res.append(n)
        return res
    for i in range(1, n+1):
        l = prime_decomp(i)
        for j in l:
            prime_list[j] += 1
    
    a,b,c,d,e = 0,0,0,0,0
    for i in prime_list:
        if i >= 74:
            a += 1
        if i >= 24:
            b += 1
        if i >= 14:
            c += 1
        if i >= 4:
            d += 1
        if i >= 2:
            e += 1
    
    res = a + b*(e-1) + c*(d-1) + d*(d-1)*(e-2)//2
    print(res)

if __name__ == '__main__':
    main()