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:
from collections import defaultdict
d = defaultdict(int)
N = int(input())
for i in range(1, N+1):
    K = i
    for j in range(2, N+1):
        if K >= j:
            while(K % j == 0):
                d[j] += 1
                K = K//j
T = defaultdict(int)
for k, v in d.items():
    if v >= 2:
        T[2] += 1
    if v >= 4:
        T[4] += 1
    if v >= 14:
        T[14] += 1
    if v >= 24:
        T[24] += 1
    if v >= 74:
        T[74] += 1

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

Submission status: Accepted

Solution code:
def fact(A):
    c0 = A
    r = 2
    lis = []
    count = 1
    while A != 1:
        if A%r == 0:
            A = A//r
            lis.append(r)
            r = 2
        else:
            r += 1
        if r > int(pow(c0,0.5))+1:
            lis.append(A)
            break
    return(lis)
n = int(input())
lis = []
for i in range(2,n+1):
    lis.extend(fact(i))
lis = sorted(lis)
L = set(lis)
import collections
c = collections.Counter(lis)
x = [0,0,0,0,0]
for R in L:
    if c[R] >= 2:
        x[0] += 1
    if c[R] >= 4:
        x[1] += 1
    if c[R] >= 14:
        x[2] += 1
    if c[R] >= 24:
        x[3] += 1
    if c[R] >= 74:
        x[4] += 1
ans = max((x[0]-2)*(x[1]-1)*x[1]//2, 0) + max((x[1]-1)*x[2], 0) + max((x[0]-1)*x[3], 0) + x[4]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
if n < 10:
  print(0)
  exit()
  
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k
 
    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
  
d = defaultdict(int)
for i in range(2,n+1):
  f = primeFactor(i)
  for j,k in f.items():
    d[j] += k

lim_74 = -1
lim_24 = -1
lim_14 = -1
lim_4 = -1
lim_2 = -1
cnt = 0
for i in d.values():
  if lim_74 == -1 and i < 74:
    lim_74 = cnt
  if lim_24 == -1 and i < 24:
    lim_24 = cnt
  if lim_14 == -1 and i < 14:
    lim_14 = cnt
  if lim_4 == -1 and i < 4:
    lim_4 = cnt
  if lim_2 == -1 and i < 2:
    lim_2 = cnt
    break
  cnt += 1
  
ans = lim_74
ans += lim_24*(lim_24-1)
ans += lim_14*(lim_14-1)
ans += lim_24*(lim_2-lim_24)
ans += lim_14*(lim_4-lim_14)
ans += lim_4*(lim_4-1)*(lim_4-2)//2
ans += lim_4*(lim_4-1)*(lim_2-lim_4)//2
print(ans)

Submission status: Accepted

Solution code:
# エラトステネスの篩
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        c = 0
        while n % p == 0:
            n //= p
            c += 1
        result.append((p, c))
    return result


N = int(input())

prime_table = make_prime_table(N)
d = {}
for i in range(2, N + 1):
    for p, c in prime_factorize(i):
        d.setdefault(p, 0)
        d[p] += c

# 75 = 5 * 5 * 3
#    = 15 * 5
#    = 25 * 3
#    = 75
n74 = 0
n24 = 0
n14 = 0
n4 = 0
n2 = 0
for k in d:
    if d[k] >= 74:
        n74 += 1
    if d[k] >= 24:
        n24 += 1
    if d[k] >= 14:
        n14 += 1
    if d[k] >= 4:
        n4 += 1
    if d[k] >= 2:
        n2 += 1

result = 0
# x ^ 4 * y ^ 4 * z ^ 2 の約数の個数は75個
result += n4 * (n4 - 1) // 2 * (n2 - 2)
# x ^ 14 * y ^ 4 の約数の個数は75個
result += n14 * (n4 - 1)
# x ^ 24 * y ^ 2 の約数の個数は75個
result += n24 * (n2 - 1)
# x ^ 74 の約数の個数は75個
result += n74
print(result)

Submission status: Accepted

Solution code:
# エラトステネスの篩
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        c = 0
        while n % p == 0:
            n //= p
            c += 1
        result.append((p, c))
    return result


N = int(input())

prime_table = make_prime_table(100)

d = {}
for i in range(2, N + 1):
    for p, c in prime_factorize(i):
        d.setdefault(p, 0)
        d[p] += c

# 75 = 5 * 5 * 3
#    = 15 * 5
#    = 25 * 3
#    = 75
n74 = 0
n24 = 0
n14 = 0
n4 = 0
n2 = 0
for k in d:
    if d[k] >= 74:
        n74 += 1
    if d[k] >= 24:
        n24 += 1
    if d[k] >= 14:
        n14 += 1
    if d[k] >= 4:
        n4 += 1
    if d[k] >= 2:
        n2 += 1

result = 0
# x ^ 4 * y ^ 4 * z ^ 2 の約数の個数は75個
result += n4 * (n4 - 1) // 2 * (n2 - 2)
# x ^ 14 * y ^ 4 の約数の個数は75個
result += n14 * (n4 - 1)
# x ^ 24 * y ^ 2 の約数の個数は75個
result += n24 * (n2 - 1)
# x ^ 74 の約数の個数は75個
result += n74
print(result)

Submission status: Accepted

Solution code:
# エラトステネスの篩
def make_prime_table(N):
    sieve = list(range(N + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(N ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, N + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


N = int(input())

prime_table = make_prime_table(100)

d = {}
for i in range(2, N + 1):
    while i != 1:
        d.setdefault(prime_table[i], 0)
        d[prime_table[i]] += 1
        i //= prime_table[i]

# 75 = 5 * 5 * 3
#    = 15 * 5
#    = 25 * 3
#    = 75
n74 = 0
n24 = 0
n14 = 0
n4 = 0
n2 = 0
for k in d:
    if d[k] >= 74:
        n74 += 1
    if d[k] >= 24:
        n24 += 1
    if d[k] >= 14:
        n14 += 1
    if d[k] >= 4:
        n4 += 1
    if d[k] >= 2:
        n2 += 1

result = 0
# x ^ 4 * y ^ 4 * z ^ 2 の約数の個数は75個
result += n4 * (n4 - 1) // 2 * (n2 - 2)
# x ^ 14 * y ^ 4 の約数の個数は75個
result += n14 * (n4 - 1)
# x ^ 24 * y ^ 2 の約数の個数は75個
result += n24 * (n2 - 1)
# x ^ 74 の約数の個数は75個
result += n74
print(result)

Submission status: Accepted

Solution code:
# エラトステネスの篩
def make_prime_table(N):
    sieve = [0] * (N + 1)
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, N + 1):
        if sieve[i] != 0:
            continue
        sieve[i] = i
        for j in range(i * i, N + 1, i):
            if sieve[j] == 0:
                sieve[j] = i
    return sieve

N = int(input())

prime_table = make_prime_table(100)

d = {}
for i in range(2, N + 1):
    while i != 1:
        d.setdefault(prime_table[i], 0)
        d[prime_table[i]] += 1
        i //= prime_table[i]

# 75 = 5 * 5 * 3
#    = 15 * 5
#    = 25 * 3
#    = 75
n74 = 0
n24 = 0
n14 = 0
n4 = 0
n2 = 0
for k in d:
    if d[k] >= 74:
        n74 += 1
    if d[k] >= 24:
        n24 += 1
    if d[k] >= 14:
        n14 += 1
    if d[k] >= 4:
        n4 += 1
    if d[k] >= 2:
        n2 += 1

result = 0
# x ^ 4 * y ^ 4 * z ^ 2 の約数の個数は75個
result += n4 * (n4 - 1) // 2 * (n2 - 2)
# x ^ 14 * y ^ 4 の約数の個数は75個
result += n14 * (n4 - 1)
# x ^ 24 * y ^ 2 の約数の個数は75個
result += n24 * (n2 - 1)
# x ^ 74 の約数の個数は75個
result += n74
print(result)

Submission status: Accepted

Solution code:
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]

N = int(input())

prime_sep = []

bigger_than4 = []
bigger_than2 = []
bigger_than74 = []
bigger_than14 = []
bigger_than24 = []

for i in primes:
    tmp = N
    if tmp//i > 0:
        count = 0
        while tmp//i > 0:
            tmp = tmp//i
            count+=tmp
        prime_sep.append([count,i])
        if count >= 4:
            bigger_than4.append([count,i])
        if count >= 2:
            bigger_than2.append([count,i])
        if count >=74:
            bigger_than74.append([count,i])
        if count >= 14:
            bigger_than14.append([count,i])
        if count >= 24:
            bigger_than24.append([count,i])

def nCr(n,r):
    if r > n:
        return 0
    ans = 1
    for i in range(n,n-r,-1):
        ans = ans*i
    for i in range(1,r+1,1):
        ans = ans//i
    return ans

res = nCr(len(bigger_than2)-len(bigger_than4),1)*nCr(len(bigger_than4),2) + 3*nCr(len(bigger_than4),3)
res+= nCr(len(bigger_than4)-len(bigger_than14),1)*nCr(len(bigger_than14),1) + 2*nCr(len(bigger_than14),2)
res+= nCr(len(bigger_than2)-len(bigger_than24),1)*nCr(len(bigger_than24),1) + 2*nCr(len(bigger_than24),2)
res+= len(bigger_than74)
print(res)

Submission status: Accepted

Solution code:
n = int(input())
yaku = [0]*101
from collections import Counter

def pf(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):
    c = pf(i)
    for j in c:
        yaku[j] += 1
        
b = Counter(yaku)
ans = 0
aa = 0
for i in range(4,101):
    aa += b[i]
    
ans += (b[2]+b[3]) * aa * (aa-1) // 2
ans += aa * (aa-1) * (aa-2) // 2

aa = 0
for i in range(74,101):
    aa += b[i]
ans += aa

aa = 0
for i in range(24,101):
    aa += b[i]
bb = 0
for i in range(2,101):
    bb += b[i]
ans += (bb-1) * aa

aa = 0
for i in range(14,101):
    aa += b[i]
bb = 0
for i in range(4,101):
    bb += b[i]
ans += (bb-1) * aa

print(ans)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
def factorize(n):
    fct={}
    temp=n
    if temp<4:
        fct[temp]=1
    else:
        e=0
        while temp%2==0:
            temp=temp//2
            e+=1
        if e>0:
            fct[2]=e
    
    for b in range(3,int(n**0.5)+1,2):
        e=0
        while temp%b == 0:
            temp=temp//b
            e+=1
        if e>0:
            fct[b]=e
    if temp!=1:
        fct[temp]=1
    return fct
dic={}
for i in range(2,n+1):
    d=factorize(i)
    for j in d:
        if j not in dic:
            dic[j]=d[j]
        else:
            dic[j]+=d[j]
n2=0
n4=0
n24=0
n14=0
n74=0
for i in dic:
    if dic[i]>=4:
        n4+=1
    if dic[i]>=2:
        n2+=1
    if dic[i]>=14:
        n14+=1
    if dic[i]>=24:
        n24+=1
    if dic[i]>=74:
        n74+=1
ans=((n4*(n4-1))//2)*(n2-2)+((n4-1)*n14)+((n2-1)*n24)+n74
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

#素因数分解
def factorization(n):
	arr = []
	tmp = n
	for i in range(2, int(-(-n**0.5//1))+1):
		if tmp%i == 0:
			cnt = 0
			while tmp%i == 0:
				cnt += 1
				tmp //= i
			arr.append([i, cnt])
	if tmp != 1:
		arr.append([tmp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr
	

N = INT()

e = [0]*(N+1)
for i in range(2, N+1):
	for x in factorization(i):
		e[x[0]] += x[1]

def num(m):
	return len([x for x in e if x >= m-1])

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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

#素因数分解
def factorization(n):
	arr = []
	tmp = n
	for i in range(2, int(-(-n**0.5//1))+1):
		if tmp%i == 0:
			cnt = 0
			while tmp%i == 0:
				cnt += 1
				tmp //= i
			arr.append([i, cnt])
	if tmp != 1:
		arr.append([tmp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr
	

N = INT()

n = [0]*(101)  #100以内の数でN!の素因数としての数

for i in range(1, N+1):
	arr = factorization(i)
	for s, t in arr:
		n[s] += t

n[1] = 0  # 1の約数は無視

num =[0]*(101)
for i in range(101):
	if 0 < n[i]:
		num[n[i]] += 1

num = list(accumulate(num[::-1]))[::-1]

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

#素因数分解
def factorization(n):
	arr = []
	tmp = n
	for i in range(2, int(-(-n**0.5//1))+1):
		if tmp%i == 0:
			cnt = 0
			while tmp%i == 0:
				cnt += 1
				tmp //= i
			arr.append([i, cnt])
	if tmp != 1:
		arr.append([tmp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr
	

N = INT()

n = [0]*101  #100以内の数でN!の素因数としての数

for i in range(1, N+1):
	arr = factorization(i)
	for s, t in arr:
		n[s] += t

n[1] = 0  # 1の約数は無視

C = Counter(n)
#print(C)
#print(C.items())

cnt_2_4 = 0
cnt_4_14 = 0
cnt_14_24 = 0
cnt_24_74 = 0
cnt_74 = 0
for p, q in C.items():
	if 2 <= p < 4:
		cnt_2_4 += q
	elif 4 <= p < 14:
		cnt_4_14 += q
	elif 14 <= p < 24:
		cnt_14_24 += q
	elif 24 <= p < 74:
		cnt_24_74 += q
	elif 74 <= p:
		cnt_74 += 1

cnt_24 = cnt_24_74 + cnt_74
cnt_14 = cnt_14_24 + cnt_24
cnt_4 = cnt_4_14 + cnt_14
cnt_2 = cnt_2_4 + cnt_4

ans = 0
ans += cnt_4*(cnt_4-1)//2 * (cnt_2-2)   # 5*5*3
ans += cnt_14 * (cnt_4-1)  #15*5
ans += cnt_24 * (cnt_2-1)  #25*3
ans += cnt_74  #75

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    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]

    def prime_array(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_p = {x:0 for x in P}
    for i in range(1,N+1):
        for p in prime_array(i):
            N_p[p] += 1
    
    # print(N_p)

    ans = 0
    for p in P:
        if N_p[p] >= 74: ans += 1
    
    for p1 in P:
        for p2 in P:
            if p1 == p2: continue
            if N_p[p1] >= 2 and N_p[p2] >= 24: ans += 1
            if N_p[p1] >= 4 and N_p[p2] >= 14: ans += 1
    
    seen = set()
    for p1 in P:
        for p2 in P:
            if p1 == p2: continue
            for p3 in P:
                if p2 == p3 or p1 == p3 or (p1,p2,p3) in seen: continue
                if N_p[p1] >= 2 and N_p[p2] >= 4 and N_p[p3] >= 4: ans += 1

                seen.add((p1,p2,p3))
                seen.add((p1,p3,p2))

    print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
pf={}
for m in range(1,n+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]=pf.get(m,0)+1
ans = 0
for k , v in pf.items():
    if v >= 74:
        ans += 1
    if v >= 24:
        for s , t in pf.items():
            if s != k and t >= 2:
                ans += 1
    if v >= 14:
        for s , t in pf.items():
            if s != k and t >= 4:
                ans += 1
    if v >= 4:
        for s , t in pf.items():
            if s > k and t >= 4:
                for f , g in pf.items():
                    if f != s and f != k and g >= 2:
                        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())


# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
#factorization(24) 
## [[2, 3], [3, 1]] 
##  24 = 2^3 * 3^1
from collections import defaultdict
d=defaultdict(int)

for i in range(1,n+1):
  x=factorization(i)
  for xi in x:
    d[xi[0]]+=xi[1]
di=defaultdict(int)
for k in d:
  if d[k]>=74:
    di[74]+=1
    di[24]+=1
    di[14]+=1
    di[4]+=1
    di[2]+=1
  elif d[k]>=24:
    di[24]+=1
    di[14]+=1
    di[4]+=1
    di[2]+=1
  elif d[k]>=14:
    di[14]+=1
    di[4]+=1
    di[2]+=1
  elif d[k]>=4:
    di[4]+=1
    di[2]+=1
  elif d[k]>=2:
    di[2]+=1
ans=di[74]
ans+=max(0,di[24]*(di[2]-1))
ans+=max(0,di[14]*(di[4]-1))
ans+=max(0,(di[4]*(di[4]-1))//2*(di[2]-2))
print(max(ans,0))

Submission status: Accepted

Solution code:
from collections import defaultdict
import math
n = int(input())
def is_prime(n):
  if n == 1:
    return False
  
  for k in range(2, int(math.sqrt(n)) + 1):
    if n%k == 0:
      return False
  return True

d = defaultdict(int)

p = []
for i in range(2,n+1):
  if is_prime(i):
    d[i] = 1
    p.append(i)
    continue
  x = i
  for j in p:
    while x%j == 0:
      x //= j
      d[j] += 1

#75
c = 0
for i in d.values():
  if i >= 74:
    c += 1
ans = c

#25 * 3
c,e = 0,0
for i in d.values():
  if i >= 24:
    c += 1
  if i >= 2:
    e += 1
ans += c*(e-1)

#15 * 5
c, e = 0, 0
for i in d.values():
  if i >= 14:
    c += 1
  if i >= 4:
    e += 1
ans += c*(e-1)

#5 * 5 * 3
c,e = 0,0
for i in d.values():
  if i >= 4:
    c += 1
  if i >= 2:
    e += 1
ans += (c*(c-1)//2)*(e-2)

print (ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
def main():
    def factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
            if temp % i == 0:
                cnt = 0
                while temp % i == 0:
                    cnt += 1
                    temp //= i
                arr.append([i, cnt])
        if temp != 1:
            arr.append([temp, 1])
        if not arr:
            arr.append([n, 1])
        return arr

    n = int(input())
    if n == 1:
        print(0)
        sys.exit()
    ps = [1] * 101
    for i1 in range(2, n + 1):
        i1fac = factorization(i1)
        for face in i1fac:
            ps[face[0]] += face[1]
    o3 = 0
    o5 = 0
    o15 = 0
    o25 = 0
    o75 = 0
    for pse in ps:
        o3 += pse >= 3
        o5 += pse >= 5
        o15 += pse >= 15
        o25 += pse >= 25
        o75 += pse >= 75
    r = o75
    r += o25 * (o3 - 1)
    r += o15 * (o5 - 1)
    if o5 >= 2:
        r += (o5 * (o5 - 1) // 2) * (o3 - 2)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def factorize_dict(n):
    b = 2
    fct = defaultdict(lambda: 0)
    while b ** 2 <= n:
        while n % b == 0:
            n //= b
            fct[b] += 1
        b += 1
    if n > 1:
        fct[n] += 1
    return fct


def main():

    N = in_n()

    prime = defaultdict(int)
    for i in range(1, N + 1):
        for k, v in factorize_dict(i).items():
            prime[k] += v

    def num(a):
        return len(list(filter(lambda x: x >= a, prime.values())))

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def factorize_dict(n):
    b = 2
    fct = defaultdict(lambda: 0)
    while b ** 2 <= n:
        while n % b == 0:
            n //= b
            fct[b] += 1
        b += 1
    if n > 1:
        fct[n] += 1
    return fct


def main():

    N = in_n()

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

    prime = defaultdict(int)
    for i in range(1, N + 1):
        for k, v in factorize_dict(i).items():
            prime[k] += v

    n2, n4, n14, n24, n74 = 0, 0, 0, 0, 0
    for k, v in prime.items():
        if v >= 2:
            n2 += 1
        if v >= 4:
            n4 += 1
        if v >= 14:
            n14 += 1
        if v >= 24:
            n24 += 1
        if v >= 74:
            n74 += 1

    ans = n74
    if n24 >= 1:
        ans += n24 * (n2 - 1)
    if n14 >= 1:
        ans += n14 * (n4 - 1)
    if n4 >= 2:
        ans += n4 * (n4 - 1) // 2 * (n2 - 2)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
N=int(input())
p=[]
dp=[[0]*100 for _ in range(100)]
dp[0][1]=1

for i in range(2,N+1):
    ti=i
    for j in range(2,i+1):
        while ti%j==0:
            p.append(j)
            ti//=j

cnt=Counter(p)
ans=0
for i,v in enumerate(cnt.values()):
    for j in range(100):
        for k in range(1,v+2):
            dp[i+1][min(76,j*k)]+=dp[i][j]
    ans=dp[i+1][75]

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()

    def sieve(num):
        isPrime = [True] * (num+1)
        isPrime[0] = isPrime[1] = False
        for i in range(2, num+1):
            if i * i > num: break
            if not isPrime[i]: continue
            for j in range(i, num+1):
                if i * j > num: break
                isPrime[i * j] = False
        return isPrime

    ps = []
    cs = []
    s = sieve(N)
    for i in range(N+1):
        if s[i]: ps.append(i)
    for p in ps:
        cc, q = 0, p
        while N//q > 0:
            cc += N//q
            q *= p
        cs.append(cc)

    ans = set()
    for i in range(len(cs)):
        if cs[i] >= 74: ans.add((pow(ps[i], 74)))

    for i in range(len(cs)):
        for j in range(len(cs)):
            if i == j: continue
            if cs[i] >= 24 and cs[j] >= 2:
                ans.add(pow(ps[i], 24) * pow(ps[j], 2))
            if cs[i] >= 14 and cs[j] >= 4:
                ans.add(pow(ps[i], 14) * pow(ps[j], 4))

    for i in range(len(cs)):
        for j in range(len(cs)):
            for k in range(len(cs)):
                if i == j or j == k or k == i: continue
                if cs[i] >= 4 and cs[j] >= 4 and cs[k] >= 2:
                    ans.add(pow(ps[i], 4) * pow(ps[j], 4) * pow(ps[k], 2))
    print(len(ans))

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
if n==1:
    print(0)
    exit()
a = [0]*(n+1)
def pf(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):
    x = pf(i)
    for j in x:
        a[j] += 1
b = [0]*5 #3,5,15,25,75
for i in a:
    if (i>=74):
        b[4]+=1
    elif (i>=24):
        b[3]+=1
    elif (i>=14):
        b[2]+=1
    elif (i>=4):
        b[1]+=1
    elif (i>=2):
        b[0]+=1
for i in range(4):
    b[3-i] += b[4-i]
ans = 0
ans += b[1]*(b[1]-1)//2*(b[0]-2)
ans += b[2]*(b[1]-1)
ans += b[3]*(b[0]-1)
ans += b[4]
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if not arr:
        arr.append([n, 1])
    return arr


def solve():
    N = int(rl())
    
    counter = defaultdict(int)
    for x in range(1, N + 1):
        facts = factorization(x)
        for fact, exp in facts:
            counter[fact] += exp
    
    M = len(counter.keys())
    nums = tuple(counter.values())
    div75 = (1, 3, 5, 15, 25, 75)
    dp = [[0] * 76 for _ in range(M + 1)]
    dp[0][1] = 1
    for i in range(M):
        for div0 in div75:
            for div1 in div75:
                if div0 * div1 <= 75 and div1 <= nums[i] + 1:
                    dp[i + 1][div0 * div1] += dp[i][div0]
    print(dp[M][75])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections

n = int(input())

# dp == [[0]*n for _ in range(75]


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


count = 0
div = {}
for i in range(2, n+1):
    c = collections.Counter(prime_factorize(i))
    for key, value in c.items():
        if key in div:
            div[key] += value
        else:
            div[key] = 1
# print(div)


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


# print(num(75))
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 numpy as np
N=int(input())
dp=[0]*(N+1)
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
for i in range(1,N+1):
  p=factorization(i)
  for x,y in p:
    dp[x]+=y
nplist=np.array(dp)
a=nplist[nplist>=2]
b=nplist[nplist>=4]
c=nplist[nplist>=14]
d=nplist[nplist>=24]
e=nplist[nplist>=74]
f=len(e)
g=len(d)*(len(a)-1)
h=len(c)*(len(b)-1)
k=len(b)*(len(b)-1)*(len(a)-2)//2
print(f+g+h+k)