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:
n = int(input())

pf_list = []
pf_list.append(n//2+ n//4+ n//8+ n//16+ n//32+ n//64)
pf_list.append(n//3+ n//9+ n//27+ n//81)
pf_list.append(n//5+ n//25)
pf_list.append(n//7+ n//49)
pf_list.append(n//11); pf_list.append(n//13); pf_list.append(n//17); pf_list.append(n//19)
pf_list.append(n//23); pf_list.append(n//29); pf_list.append(n//31); pf_list.append(n//37)
pf_list.append(n//41); pf_list.append(n//43); pf_list.append(n//47)


a = [1 if i >= 74 else 0 for i in pf_list]
b = [1 if i >= 24 else 0 for i in pf_list]
c = [1 if i >= 14 else 0 for i in pf_list]
d = [1 if i >= 4 else 0 for i in pf_list]
e = [1 if i >= 2 else 0 for i in pf_list]

ans = 0
for i in range(15):
    for j in range(15):
        if i == j:
            continue
        for k in range(j):
            if i == k:
                continue
            ans += e[i]*d[j]*d[k]
for i in range(15):
    for j in range(15):
        if i == j:
            continue
        ans += e[i]*b[j]
for i in range(15):
    for j in range(15):
        if i == j:
            continue
        ans += d[i]*c[j]
for i in range(15):
    ans += a[i]

print(ans)

Submission status: Accepted

Solution code:
import collections
import functools
import itertools
import math
import operator


N = int(input())


def get_prime_factorized(N):
    R = []
    b, e = 2, 0
    while b ** 2 <= N:
        while N % b == 0:
            N  = N // b
            e += 1
        if e > 0:
            R.append([b, e])
        b, e = b + 1, 0
    if N > 1:
        R.append([N, 1])
    return R

def n_C_r(n, r):
    return int(math.factorial(n) / math.factorial(r) / math.factorial(n-r))

if N > 9:
    L = [l[1]+1 for l in get_prime_factorized(math.factorial(N))]
    L = [[3, 5, 15, 25, 75] if l >= 75 else [3, 5, 15, 25] if l >= 25 else [3, 5, 15] if l >= 15 else [3, 5] if l >= 5 else [3] if l >= 3 else [1] for l in L]
    L = [l for l in L if l != [1]]
    L = list(itertools.chain.from_iterable(L))
    C = collections.Counter(L)

    R = C[75] + n_C_r(C[5], 2) * n_C_r(C[3]-2, 1) + C[25] * (C[3] - 1) + C[15] * (C[5] - 1)

    print(R)
else:
    print(0)

Submission status: Accepted

Solution code:
N = int(input())

primes = {}

for i in range(2, N+1):
    tmpN = i
    n = 2
    while tmpN > 1:
        while tmpN%n == 0:
            tmpN //= n
            if n in primes:
                primes[n] += 1
            else:
                primes[n] = 1
        n += 1

kumi5 = 0
kumi3 = 0
kumi75 = 0
kumi25 = 0
kumi15 = 0
for key in primes.keys():
    if primes[key] >= 74:
        kumi75 += 1
    if primes[key] >= 24:
        kumi25 += 1
    if primes[key] >= 14:
        kumi15 += 1
    if primes[key] >= 4:
        kumi5 += 1
    if primes[key] >= 2:
        kumi3 += 1


ans = 0
if kumi5 >= 2 and kumi3 >= 3:
    ans += (kumi5 * (kumi5-1) // 2) * (kumi3-2)

if kumi75 >= 1:
    ans += kumi75

if kumi25 >= 1 and kumi3 >= 2:
    ans += kumi25 * (kumi3-1)

if kumi15 >= 1 and kumi5 >= 2:
    ans += kumi15 * (kumi5-1)

print(ans)

Submission status: Accepted

Solution code:
def f2(p):
    return 2*p
def f4(p):
    if p<5:
        return 3*p
    else:
        return 4*p
def f14(p):
    if p==2:
        return 16
    elif p==3:
        return 30
    elif p==5:
        return 60
    elif p==7:
        return 91
    else:
        return 101
def f24(p):
    if p==2:
        return 28
    elif p==3:
        return 54
    elif p==5:
        return 100
    else:
        return 101
def f74(p):
    if p==2:
        return 78
    else:
        return 101
    
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]

N = int(input())
c2=0
c4=0
c14=0
c24=0
c74=0

for p in P:
    if f2(p)<=N:
        c2 += 1
    if f4(p)<=N:
        c4 += 1
    if f14(p)<=N:
        c14 += 1
    if f24(p)<=N:
        c24 += 1
    if f74(p)<=N:
        c74 += 1


ans = 0
ans += (c4*(c4-1)//2)*(c2-2)
ans += c14 * (c4 - 1)
ans += c24 * (c2 - 1)
ans += c74

print(ans)

Submission status: Accepted

Solution code:
#! usr/bin/env python
# -*- coding: utf-8 -*-

res = {}
dp = [[0 for j in range(80)] for i in range(30)]


def pf(n):
    c = 2
    while c * c <= n:
        while not n % c:
            res[c] = res.get(c, 0) + 1
            n //= c
        c += 1

    if n != 1:
        res[n] = res.get(n, 0) + 1


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

    for i in range(2, n+1):
        pf(i)

    a = [res[k] for k in res]
    for i in range(30):
        dp[i][1] = 1
    for i in range(len(a)):
        for j in range(80):
            dp[i+1][j] = dp[i][j]
            for k in range(1, min(a[i]+1, j+1)):
                if not j % (k+1):
                    dp[i+1][j] += dp[i][j//(k+1)]

    print(dp[len(a)][75])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def prime_factors(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
    
a = int(input())
fac = dict()
for i in range(a + 1):
	for k in prime_factors(i):
		if k not in fac:
			fac[k]  = 1
		else:
			fac[k] += 1

for i in list(fac):
	if fac[i] == 1:
		fac.pop(i)

out = 0
for i in fac:
	if fac[i] >= 74:
		out += 1
		
for i in fac:
	if fac[i] >= 24:
		for j in fac:
			if i != j and fac[j] >= 2:
				out += 1
					
for i in fac:
	if fac[i] >= 14:
		for j in fac:
			if i != j and fac[j] >= 4:
				out += 1
		
used = dict()
for i in fac:
	if fac[i] >= 4:
		for j in fac:
			if i != j and tuple(sorted([i,j])) not in used and fac[j] >= 4:
				used[tuple(sorted([i,j]))] = 1
				for k in fac:
					if k != i and k != j and fac[k] >= 2:
						out += 1

print(out)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
primes = defaultdict(int)
for i in range(N):
  n = i + 1
  p = 2
  while n >= p:
    while n % p == 0:
      primes[p] += 1
      n //= p
    p += 1
  if n > 1:
    primes[n] += 1
P = [0, 0, 0, 0, 0]
for p, v in primes.items():
  if v >= 74:
    P[0] += 1
  elif v >= 24:
    P[1] += 1
  elif v >= 14:
    P[2] += 1
  elif v >= 4:
    P[3] += 1
  elif v >= 2:
    P[4] += 1
for i in range(4):
  P[i + 1] += P[i]
cnt = 0
cnt += P[0]
cnt += P[1] * (P[4] - 1)
cnt += P[2] * (P[3] - 1)
cnt += P[3] * (P[3] - 1) // 2 * (P[4] - 2)
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import combinations

def factorize(n, fct):
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct[b] += e
        b, e = b + 1, 0
    if n > 1:
        fct[n] += 1
    return fct


N = int(input())
d = defaultdict(lambda: 0)
for i in range(N+1):
    d = factorize(i, d)


keys = list(d.keys())

certificates = []

for k in keys:
    if d[k] >= 2:
        certificates.append(k)


res = 0
        
for i,j,k in combinations(certificates, 3):
    if d[j] >= 4 and d[k] >= 4:
        res += 1
    if d[i] >= 4 and d[k] >= 4:
        res += 1
    if d[i] >= 4 and d[j] >= 4:
        res += 1

for i,j in combinations(certificates, 2):
    if d[i] >= 24:
        res += 1
    if d[j] >= 24:
        res += 1
        
for i,j in combinations(certificates, 2):
    if d[i] >= 4 and d[j] >= 14:
        res += 1
    if d[j] >= 4 and d[i] >= 14:
        res += 1
    
for i in certificates:
    if d[i] >= 74:
        res += 1

print(res)

Submission status: Accepted

Solution code:
import math

def is_prime(n):
    if n==1:
        return False
    for i in range(n-2):
        if n % (i+2) == 0:
            return False
    return True

prime_list = []
for i in range(100):
    if is_prime(i+1):
        prime_list.append(i+1)


factor_list = [0] * len(prime_list)

N = int(input())

for i in range(N):
    for p in prime_list:
        j = i+1
        while j % p == 0:
            factor_list[prime_list.index(p)] += 1
            j = j / p

ans = 0
for i in range(len(factor_list)):
    if factor_list[i] >= 74:
        ans += 1

cnta = 0
cntb = 0
for i in range(len(factor_list)):
    if factor_list[i] >= 14:
        cnta += 1
    if factor_list[i] >= 4:
        cntb += 1
ans += cnta * (cntb-1)

cnta = 0
cntb = 0
for i in range(len(factor_list)):
    if factor_list[i] >= 24:
        cnta += 1
    if factor_list[i] >= 2:
        cntb += 1
ans += cnta * (cntb-1)

cnta = 0
cntb = 0
for i in range(len(factor_list)):
    if factor_list[i] >= 4:
        cnta += 1
    if factor_list[i] >= 2:
        cntb += 1
ans += cnta * (cnta-1) * (cntb-2) /2

print(int(ans))

Submission status: Accepted

Solution code:
# encoding: utf-8
import sys

N = int(input())

# p ** a
ptab = [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, 101]
atab = [1] * (N + 1) # prime factor upper == N ?

# create atab
memo = [None] * (N + 1)
pidx = 0
cnt = 0
for i in range(2, N + 1):
    tmp = i
    # for p in range(2, N + 1):
    for p in ptab:
        # escape
        if tmp in ptab:
            atab[tmp] += 1
            break
        elif tmp < 2: break
        elif tmp % p > 0: continue
        # solve a
        for a in range(1, N):
            cnt += 1
            if tmp % (p ** (a + 1)) > 0: break
        # update atab
        tmp = tmp // (p ** a)
        atab[p] += a
        # print("#", i, p, cnt)

# remove 1
atab_small = []
for maxa in atab:
    if maxa > 1: atab_small.append(maxa)
N = len(atab_small)
# print("#", atab_small)

def count(pos, val):
    if pos == N or val == 75: return 0
    ret = 0
    for atmp in range(1, atab_small[pos] + 1): # include a + 1
        if atmp not in [1, 3, 5, 15, 25, 75]: continue
        val_tmp = val * atmp
        if val_tmp < 75: ret += count(pos + 1, val_tmp)
        elif val_tmp == 75: ret += 1
        else: break
    return ret

print(count(0, 1))

Submission status: Accepted

Solution code:
N = int( input())
W = [0]*101
for i in range(2,N+1):
    j = i
    for k in range(2,100):
        while j%k == 0:
            W[k] += 1
            j //= k
ans = 0
if N >= 78:
    ans += 1
for i in range(2,N+1):
    if W[i] >= 2:
        for j in range(2,N+1):
            if j == i:
                continue
            if W[j] >= 24:
                ans += 1
for i in range(2,N+1):
    if W[i] >= 4:
        for j in range(2,N+1):
            if j == i:
                continue
            if W[j] >= 14:
                ans += 1

for i in range(2,N+1):
    if W[i] >= 2:
        for j in range(2,N+1):
            if j == i:
                continue
            if W[j] >= 4:
                for k in range(j,N+1):
                    if k == i or k == j:
                        continue
                    if W[k] >= 4:
                        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import combinations


def prime_factors(n):
    c = Counter()
    while n > 1:
        for i in range(2, n + 1):
            if n % i == 0:
                c.update([i])
                n //= i
                break
    return c


def factrials(n):
    c = {}
    for i in range(2, n + 1):
        d = prime_factors(i)
        for k, v in d.items():
            if k in c:
                c[k] += v
            else:
                c[k] = v
    return c


def solve(N):
    facts = factrials(N)
    over2 = [k for k, v in facts.items() if v >= 2]
    over4 = [k for k, v in facts.items() if v >= 4]
    over14 = [k for k, v in facts.items() if v >= 14]
    over24 = [k for k, v in facts.items() if v >= 24]
    over74 = [k for k, v in facts.items() if v >= 74]

    sum = 0
    # 4 - 4 - 2
    sum += len([(d, d4) for d in over2 for d4 in combinations(over4, 2) if d not in d4])
    # 4 - 14
    sum += len([(d, d4) for d in over14 for d4 in over4 if d != d4])
    # 2 - 24
    sum += len([(d, d2) for d in over24 for d2 in over2 if d != d2])
    # 74
    sum += len(over74)

    return sum

if __name__ == "__main__":
    print(solve(int(input())))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations
n = int(input())

primes = []
for i in range(1,n+1):
    z = 2
    while z<=i:
        while i%z==0:
            i //= z
            primes.append(z)
        z += 1

d = {}
for x in primes:
    if x not in d:
        d[x] = 0
    d[x] += 1

keys = list(d.keys())
res = 0

for k in keys:
    if d[k]>=74:
        res += 1
if len(keys)>=2:
    for c in combinations(keys,2):
        if d[c[0]]>=24 and d[c[1]]>=2:
            res += 1
        if d[c[0]]>=2 and d[c[1]]>=24:
            res += 1

        if d[c[0]]>=4 and d[c[1]]>=14:
            res += 1
        if d[c[0]]>=14 and d[c[1]]>=4:
            res += 1
if len(keys)>=3:
    for c in combinations(keys, 3):
        if d[c[0]]>=4 and d[c[1]]>=4 and d[c[2]]>=2:
            res += 1
        if d[c[0]]>=4 and d[c[1]]>=2 and d[c[2]]>=4:
            res += 1
        if d[c[0]]>=2 and d[c[1]]>=4 and d[c[2]]>=4:
            res += 1
print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict
N=int(input())
def factorint(x):
  F={}
  i=2
  while i**2<=x:
    if x%i==0:
      c=0
      while x%i==0:
        x=x//i
        c+=1
      F[i]=c
    i+=1
  if x!=1:
    F[x]=1
  return F

A=defaultdict(int)
for i in range(2,N+1):
  for p,q in factorint(i).items():
    A[p]+=q

num2=0
num4=0
num14=0
num24=0
num74=0
for p,q in A.items():
  if q>=2:
    num2+=1
  if q>=4:
    num4+=1
  if q>=14:
    num14+=1
  if q>=24:
    num24+=1
  if q>=74:
    num74+=1
    
ans=0
ans+=(num2-2)*(num4)*(num4-1)//2
ans+=(num2-1)*(num24)
ans+=(num4-1)*(num14)
ans+=num74
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
def factorize(n):
    fct0 =fct1 =fct2 =fct3 =fct4 = 0  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if 2<=e<4:
            fct0+=1
        elif 4<=e<14:
            fct1+=1
        elif 14<=e<24:
            fct2+=1
        elif 24<=e<74:
            fct3+=1
        elif 74<=e:
            fct4+=1
        b, e = b + 1, 0
    return [fct0,fct1,fct2,fct3,fct4]
from math import factorial
l=factorize(factorial(n))
ans=l[4]
ans+=(l[3]+l[4])*max(sum(l)-1,0)
ans+=(l[2]+l[3]+l[4])*max(sum(l)-l[0]-1,0)
ans+=(sum(l)-l[0])*max(sum(l)-l[0]-1,0)*max(sum(l)-2,0)//2
print(int(ans))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
              41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

    prime_factors = {k: 0 for k in primes}

    for i in range(1, N+1):
        for p in primes:
            while i % p == 0:
                prime_factors[p] += 1
                i //= p
    retval = 0
    patterns = [[75], [25, 3], [15, 5], [5, 5, 3]]
    memo = []
    for pattern in patterns:
        stack = [(pattern, {})]
        while len(stack):
            remaining, used = stack.pop()
            if len(remaining) == 0:
                if used not in memo:
                    retval += 1
                    memo.append(used)
                continue
            for p in primes:
                if prime_factors[p] >= remaining[0] - 1 and p not in used:
                    next_used = {k: used[k] for k in used}
                    next_used[p] = remaining[0] - 1
                    stack.append((remaining[1:], next_used))
    print(retval)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
ps = [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]
cnts = []
ans = 0

for p in ps:
    cnt = 0
    for i in range(1,100):
        add = n//(p**i)
        if add != 0:
            cnt += add
        else:
            break
    cnts.append(cnt)

# 75
ans += sum(1 if x>=74 else 0 for x in cnts)

# 25 * 3
ans += sum(1 if x>=24 else 0 for x in cnts) * (sum(1 if x>=2 else 0 for x in cnts) - 1)

# 15 * 5
ans += sum(1 if x>=14 else 0 for x in cnts) * (sum(1 if x>=4 else 0 for x in cnts) - 1)

# 5 * 5 * 3
ans += (sum(1 if x>=4 else 0 for x in cnts) * (sum(1 if x>=4 else 0 for x in cnts) - 1) * (sum(1 if x>=2 else 0 for x in cnts) - 2)) // 2

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
from collections import Counter

# 高速 組み合わせ
def C(n, r):
  a = 1
  b = 1
  for i in range(r):
    a = a*(n-i)
    b = b*(r-i)
  return((a//b))

N = int(input())

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
        primfac.append(n)
    return primfac

# tmp = [[75],[5,5,3],[25,3],[15,5]]
cnt = Counter(primes(math.factorial(N)))
# cnt = Counter(primes(N))
ans = 0
ans += sum([1 for k,v in cnt.items() if v >= 74])

t1 = sum([1 for k, v in cnt.items() if v >= 24])
t2 = sum([1 for k, v in cnt.items() if v >= 2])

ans += t1 * (t2 - 1)

t1 = sum([1 for k, v in cnt.items() if v >= 14])
t2 = sum([1 for k, v in cnt.items() if v >= 4])

ans += t1 * (t2 - 1)

t3 = sum([1 for k, v in cnt.items() if v >= 4])
if t3 >= 2:
    t1 = C(t3,2)
    t2 = sum([1 for k, v in cnt.items() if v >= 2])

    ans += t1 * (t2 - 2)

# print(cnt)
print(ans)

Submission status: Accepted

Solution code:
import math
import functools

TARGET = 75

def main():
    l = [0]
    for j in range(1, 101):
        f = math.factorial(j)
        primes = prime_factorization(f)
        primes = [x for _, x in primes.items()]
        counts = []
        for i, _ in enumerate(primes):
            counts.append(0)
        l.append(count_divisor(primes, counts, 0, 0))
        print(j)
        print(l, flush=True)
    print(l)

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

def prime_factorization(number):
    n = number
    i = 2
    factor = {}
    while i * i <= n:
        while n % i == 0:
            if i in factor:
                factor[i] += 1
            else:
                factor.update({i : 1})
            n //= i
        i += 1
    if n > 1 or not factor:
        if n in factor:
            factor[n] += 1
        else:
            factor.update({n : 1})
    return factor

def count_divisor(primes, counts, current, count):
    divisors = functools.reduce(lambda x, y: x*(y+1), counts, 1)
    if divisors >= TARGET:
        if divisors == TARGET:
            return count + 1
        else:
            return count
    new_counts = list(counts)
    for i in range(current, len(counts)):
        if counts[i] >= primes[i]:
            continue
        new_counts[i] += 1
        count = count_divisor(primes, new_counts, i, count)
        new_counts[i] -= 1
    return count

if __name__ == '__main__':
    #main()
    answer()

Submission status: Accepted

Solution code:
from math import floor, sqrt
from collections import Counter
from itertools import permutations

def getPrimeFactor(x):
    ans = []
    for d in range(2, floor(sqrt(x)) + 1):
        while x % d == 0:
            ans.append(d)
            x //= d
    if x != 1:
        ans.append(x)
    return ans

N = int(input())

cntP = Counter()
for x in range(2, N + 1):
    PF = getPrimeFactor(x)
    cntP.update(PF)

As = cntP.values()
ans = 0
for A1, A2, A3 in permutations(As, 3):
    if A1 >= 2 and A2 >= 4 and A3 >= 4: ans += 1
ans //= 2

for A1, A2 in permutations(As, 2):
    if A1 >= 4 and A2 >= 14: ans += 1
    if A1 >= 2 and A2 >= 24: ans += 1

for A in As:
    if A >= 74: ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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]
M = {}

for i in P:
	M[i] = 0

N = int(input())
for p in P:
	i = 1
	s = 0
	while(True):
		t = int(N/(p**i))
		if t == 0:
			break
		s += t
		i+=1
	M[p] = s

k2 = 0
k4 = 0
k14 = 0
k24 = 0
k74 = 0

for i in M.values():
	if 74 <= i:
		k74+=1
	if 24 <= i:
		k24+=1
	if 14 <= i:
		k14+=1
	if 4 <= i:
		k4+=1
	if 2 <= i:
		k2+=1

print(int(k74 + k24*(k2-1) + k14*(k4-1)+ (k2-2)*k4*(k4-1)/2))

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import combinations


# time complexity: O(√n)
def prime_factorize(n, prime_factors=None):
    if prime_factors is None:
        prime_factors = defaultdict(int)
    i = 2
    while i * i <= n:
        if n % i == 0:
            while n % i == 0:
                prime_factors[i] += 1
                n //= i
        i += 1
    if n != 1:
        prime_factors[n] += 1
    return prime_factors


N = int(input())
prime_factors = defaultdict(int)
for n in range(1, N + 1):
    prime_factors = prime_factorize(n, prime_factors)

over_primes = defaultdict(list)
for p, e in prime_factors.items():
    for threshold in (2, 4, 14, 24, 74):
        if e >= threshold:
            over_primes[threshold].append(p)
num_shichigos = 0
for p1 in over_primes[2]:
    # (2, 4, 4)
    for p2_1, p2_2 in combinations(over_primes[4], 2):
        if p1 != p2_1 and p1 != p2_2:
            num_shichigos += 1
    # (2, 24)
    for p3 in over_primes[24]:
        if p1 != p3:
            num_shichigos += 1
for p1 in over_primes[4]:
    # (4, 14)
    for p2 in over_primes[14]:
        if p1 != p2:
            num_shichigos += 1
# (74)
num_shichigos += len(over_primes[74])
print(num_shichigos)

Submission status: Accepted

Solution code:
N = int(input())
ret = 0
prime_list = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
if N >= 78:
    ret += 1
if N >= 28:
    ret += len([a for a in prime_list if 2 * a <= N]) - 1
if N >= 54:
    ret += len([a for a in prime_list if 2 * a <= N]) - 1
if N >= 100:
    ret += len([a for a in prime_list if 2 * a <= N]) - 1
if N >= 16:
    ret += len([a for a in prime_list if 4 * a <= N]) - 1
if N >= 30:
    ret += len([a for a in prime_list if 4 * a <= N]) - 1
if N >= 60:
    ret += len([a for a in prime_list if 4 * a <= N]) - 1
if N >= 91:
    ret += len([a for a in prime_list if 4 * a <= N]) - 1
if 9 <= N < 20:
    ret += len([a for a in prime_list if 2 * a <= N]) - 2
if N >= 20:
    temp = len([a for a in prime_list if 4 * a <= N])
    temp2 = int(temp * (temp - 1) / 2 + 0.1)
    ret += temp2 * (len([a for a in prime_list if 2 * a <= N]) - 2)
print(str(ret))

Submission status: Accepted

Solution code:
n = int(input())
primelist = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
v = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for i in range(15):
    e = primelist[i]
    k = n
    while k != 0:
        k = k // e
        v[i] += k

x2 = 0
x4 = 0
x14 = 0
x24 = 0
x74 = 0
for e in v:
    if e >= 2:
        x2 += 1
for e in v:
    if e >= 4:
        x4 += 1
for e in v:
    if e >= 14:
        x14 += 1
for e in v:
    if e >= 24:
        x24 += 1
for e in v:
    if e >= 74:
        x74 += 1


sum = 0
sum += max(0, x4 * (x4 - 1) * (x2 - 2) // 2)
sum += max(0, x24 * (x2 - 1))
sum += max(0, x14 * (x4 - 1))
sum += x74
print(sum)

Submission status: Accepted

Solution code:
n=int(input())
c=0
c2=0;c3=0;c5=0;c7=0;c11=0;c13=0;c17=0;c19=0;c23=0;c29=0;c31=0;c37=0;c41=0;c43=0;c47=0
for i in range(2,n+1):
  if i%64==0:c2+=6
  elif i%32==0:c2+=5
  elif i%16==0:c2+=4
  elif i%8==0:c2+=3
  elif i%4==0:c2+=2
  elif i%2==0:c2+=1
  if i%81==0:c3+=4
  elif i%27==0:c3+=3
  elif i%9==0:c3+=2
  elif i%3==0:c3+=1
  if i%25==0:c5+=2
  elif i%5==0:c5+=1
  if i%49==0:c7+=2
  elif i%7==0:c7+=1
  if i%11==0:c11+=1
  if i%13==0:c13+=1
  if i%17==0:c17+=1
  if i%19==0:c19+=1
  if i%23==0:c23+=1
  if i%29==0:c29+=1
  if i%31==0:c31+=1
  if i%37==0:c37+=1
  if i%41==0:c41+=1
  if i%43==0:c43+=1
  if i%47==0:c47+=1
l=[c2,c3,c5,c7,c11,c13,c17,c19,c23,c29,c31,c37,c41,c43,c47]
if max(l)>=74:
  c+=1
if max(l)>=24:
  a=0;b=0
  for j in range(len(l)):
    if l[j]>=24:a+=1
    elif l[j]>=2:b+=1
  c+=a*(a+b-1)
if max(l)>=14:
  e=0;f=0
  for k in range(len(l)):
    if l[k]>=14:e+=1
    elif l[k]>=4:f+=1
  c+=e*(e+f-1)
if max(l)>=2:
  g=0;h=0
  for m in range(len(l)):
    if l[m]>=4:g+=1
    elif l[m]>=2:h+=1
  if g>=2:
    x=int((g*(g-1))/2)
    c+=x*(g+h-2)
print(c)

Submission status: Accepted

Solution code:
import itertools
factorDictionary = {}
plist = [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]
for p in plist:
    factorDictionary[p] = 0
N = int(input())
for i in range(1,N+1):
    x = i
    for p in plist:
        while x%p == 0:
            factorDictionary[p] += 1
            x /= p
triples = itertools.combinations(plist,3)
doubles = itertools.combinations(plist,2)
answer = 0
for triple in triples:
    addedValue = 0
    for a,b,c in itertools.permutations(triple,3):
        p = factorDictionary[a]
        q = factorDictionary[b]
        r = factorDictionary[c]
        if p>=4 and q>=4 and r>=2:
            addedValue += 1
    answer += addedValue//2
for double in doubles:
    for a,b in itertools.permutations(double,2):
        p = factorDictionary[a]
        q = factorDictionary[b]
        if p>=14 and q>=4:
            answer +=1
        if p>=24 and q>=2:
            answer +=1
for a in plist:
    if factorDictionary[a] >= 74:
        answer += 1
print(answer)

Submission status: Accepted

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

def sel2(f, a, b):
    g = [(k, v) for k, v in f.items() if v >= a]
    res = 0
    for ik, iv in g:
        for jk, jv in g:
            if ik == jk: continue
            if jv < b: continue
            res += 1
    return res

def sel3(f, a, b, c):
    g = [(k, v) for k, v in f.items() if v >= a]
    res = 0
    for ik, iv in g:
        for jk, jv in g:
            if ik == jk: continue
            if jv < b: continue
            for kk, kv in g:
                if kk in (ik, jk): continue
                if kk < jk: continue
                if kv < c: continue
                res += 1
    return res

n = int(input())
facs = {}
for i in range(2, n+1):
    tmp = factors(i)
    for k, v in tmp.items():
        if k in facs: facs[k] += v
        else: facs[k] = v

res = 0
res += sum(1 for k, v in facs.items() if v >= 74)
res += sel2(facs, 2, 24)
res += sel2(facs, 4, 14)
res += sel3(facs, 2, 4, 4)
print(res)

Submission status: Accepted

Solution code:
n = int(input())

ps = [2]
for i in range(3, 100, 2):
    f = True
    for j in range(2, i):
        if i < j * j:
            break
        elif i % j == 0:
            f = False
            break
    if f:
        ps.append(i)

ls = [0 for _ in range(len(ps))]
for i in range(2, n + 1):
    k = i
    for j in range(len(ps)):
        while k % ps[j] == 0:
            ls[j] += 1
            k //= ps[j]

ans = 1 if 74 <= ls[0] else 0

for i in range(len(ps)):
    for j in range(len(ps)):
        if i == j:
            continue
        if 2 <= ls[i] and 24 <= ls[j]:
            ans += 1
        if 4 <= ls[i] and 14 <= ls[j]:
            ans += 1

for i in range(len(ps)):
    for j in range(len(ps) - 1):
        if i == j:
            continue
        for k in range(j + 1, len(ps)):
            if i == k:
                continue
            if 2 <= ls[i] and 4 <= ls[j] and 4 <= ls[k]:
                ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math
def factorization(n):
    def factor_sub(n, m):
        c = 0
        while n % m == 0:
            c += 1
            n //= m
        return c, n
    #
    buff = []
    c, m = factor_sub(n, 2)
    if c > 0: buff.append((2, c))
    c, m = factor_sub(m, 3)
    if c > 0: buff.append((3, c))
    x = 5
    while m >= x * x:
        c, m = factor_sub(m, x)
        if c > 0: buff.append((x, c))
        if x % 6 == 5:
            x += 2
        else:
            x += 4
    if m > 1: buff.append((m, 1))
    return buff
#a = factorization(n)
#b = []
#for i,j in a:
#  b.append(i)
def divisor_sub(p, q):
    a = []
    for i in range(0, q + 1):
        a.append(p ** i)
    return a

def divisor(n):
    if n == 1:
      return([1])
    xs = factorization(n)
    ys = divisor_sub(xs[0][0], xs[0][1])
    for p, q in xs[1:]:
        ys = [x * y for x in divisor_sub(p, q) for y in ys]
    return sorted(ys)
n = int(input())
a = 1
for i in range(1,n+1):
  a*=i
x = factorization(a)
y = []
for i,j in x:
  y.append(j)
ans = 0
for i in y:
  if i >= 74:
    ans += 1
san = 0
go = 0
for i in y:
  if i >= 2:
    san += 1
  if i >= 4:
    go += 1
for i in y:
  if i>=24:
    ans += san-1
  if i >= 14:
    ans += go-1
ans += go*(go-1)//2*(san-2)
print(ans)

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)
fct = [0 for p in primes]

def factorize(n):
    result = [0 for p in primes]
    for i, p in enumerate(primes):
        while n % p == 0:
            n = n // p
            result[i] += 1

    return result


def main():
    N = int(input())
    for n in range(1, N+1):
        fct_n = factorize(n)
        for i in range(len(fct_n)):
            fct[i] += fct_n[i]
    c75 = len([f for f in fct if f >= 74])
    c25 = len([f for f in fct if f >= 24])
    c15 = len([f for f in fct if f >= 14])
    c5 = len([f for f in fct if f >= 4])
    c3 = len([f for f in fct if f >= 2])

    result = 0
    result += c75
    result += c25 * (c3 - 1)
    result += c15 * (c5 - 1)
    result += (c5 * (c5 - 1)) // 2 * (c3 - 2)

    print(result)


if __name__ == '__main__':
    main()