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())
from sys import exit
if n == 1:
  print(0)
  exit()

from collections import defaultdict as dd
dic_list = [{}, {}, {2: 1}]
def prime_factrization(num):  
  dic = dd(lambda: 0)
  for i in range(2, int(num**0.5) + 2):
    mod = num % i
    while mod == 0:
      num //= i
      dic[i] += 1
      mod = num % i
    if num == 1:
      break
  else:
    if num != 1:
      dic[num] += 1
  return dic

dic = dd(lambda: 0)
for i in range(2, n+1):
  pf = prime_factrization(i)
  for j in range(2, 100):
    dic[j] += pf[j]
#print(dic)

#75 = 5 * 5 * 3
up3_divisor = 0
for num in dic.values():
  if num >= 2:
    up3_divisor += 1
up5_divisor = 0
for num in dic.values():
  if num >= 4:
    up5_divisor += 1
up15_divisor = 0
for num in dic.values():
  if num >= 14:
    up15_divisor += 1
up25_divisor = 0
for num in dic.values():
  if num >= 24:
    up25_divisor += 1
up75_divisor = 0
for num in dic.values():
  if num >= 74:
    up75_divisor += 1

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
ans = 0
if up75_divisor >= 1:
  ans += combinations_count(up75_divisor, 1) #75
if up25_divisor >= 1:
  ans += combinations_count(up25_divisor, 1) * (combinations_count(up3_divisor, 1) - 1) #25 * 3
if up15_divisor >= 1:
  ans += combinations_count(up15_divisor, 1) * (combinations_count(up5_divisor, 1) - 1) #15 * 5
if up5_divisor >= 2:
  ans += combinations_count(up5_divisor, 2) * (combinations_count(up3_divisor, 1) - 2) #5 * 5 * 3
print(ans)

Submission status: Accepted

Solution code:
# 素因数分解によってx=p**n+q**m+...と表せるとき、
# 約数の個数は(n+1)*(m+1)*...
# つまり、約数が75個(素因数分解すると3*5*5)あるというのは素数が
# [2, 4, 4]個ずつor[4, 14]個ずつor[2, 24]個ずつor[74]個ある組み合わせを数えればよい

from collections import Counter, defaultdict
from itertools import product

n = int(input())

def prime_factorization(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

prime = []
for i in range(1, n+1):
    prime += prime_factorization(i)
    
ctr = Counter(prime)

# 各素数が[2, 4, 14, 24, 74]個以上ある素数を求める
d = defaultdict(list)
for k, v in ctr.items():
    for p in [2, 4, 14, 24, 74]:
        if v >= p:
            d[p].append(k)
        else:
            break

            
# 組み合わせ(重複している組みあわせはcontiue)
comb_num = 0
for comb in [[2, 4, 4], [4, 14], [2, 24], [74]]:
    for prime_comb in list(product(*[d[c] for c in comb])):
        if len(prime_comb) != len(set(prime_comb)):
            continue
        if comb == [2, 4, 4] and prime_comb[1] < prime_comb[2]:
            continue
        comb_num += 1
print(comb_num)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations
U = 101
T = np.zeros(U,np.int32)
T[2] = 1
T[3::2] = 1
for i in range(U):
  if i*i>U:
    break
  if T[i]==1:
    T[i*i::2*i] = 0
N = int(input())
pls = np.where(T)[0].tolist()
dic = {}
for i in range(1,N+1):
  for p in pls:
    cnt = 0
    while i%p==0:
      i //= p
      cnt += 1
    dic[p] = dic.get(p,0)+cnt
ans = 0
for a,b,c in combinations(pls,3):
  if 2<=dic[a] and 4<=dic[b] and 4<=dic[c]:
    ans += 1
  if 4<=dic[a] and 2<=dic[b] and 4<=dic[c]:
    ans += 1
  if 4<=dic[a] and 4<=dic[b] and 2<=dic[c]:
    ans += 1
for a, b in combinations(pls,2):
  if 4<=dic[a] and 14<=dic[b]:
    ans += 1
  if 14<=dic[a] and 4<=dic[b]:
    ans += 1
  if 2<=dic[a] and 24<=dic[b]:
    ans += 1
  if 24<=dic[a] and 2<=dic[b]:
    ans += 1

for a in pls:
  if 74<=dic[a]:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import permutations as p

def factorize(n):
    d = defaultdict(int)
    for i in range(2, int(n**0.5)+1):
        while n%i==0:
            d[i] += 1
            n //= i
        if not n:
            break
    if n>1:
        d[n] += 1
    return d

N = int(input())
d = Counter()
for i in range(1, N+1):
    d += factorize(i)
vl = d.values()

ans = sum(1 for i, j, k in p(vl, 3) if i>=2 and j>=4 and k>=4)//2
ans += sum(1 for i, j in p(vl, 2) if i>=2 and j>=24)
ans += sum(1 for i, j in p(vl, 2) if i>=4 and j>=14)
ans += sum(1 for i in vl if i>=74)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from itertools import permutations as p

def factorize(n):
    d = dd(int)
    for i in range(2, int(n**0.5)+1):
        while n%i==0:
            d[i] += 1
            n //= i
        if not n:
            break
    if n>1:
        d[n] += 1
    return d

N = int(input())
d = dd(int)
for i in range(1, N+1):
    e = factorize(i)
    for i,j in e.items():
        d[i] += j
vl = d.values()

ans = sum(1 for i, j, k in p(vl, 3) if i>=2 and j>=4 and k>=4)//2
ans += sum(1 for i, j in p(vl, 2) if i>=2 and j>=24)
ans += sum(1 for i, j in p(vl, 2) if i>=4 and j>=14)
ans += sum(1 for i in vl if i>=74)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from itertools import permutations as p

def factorize(n):
    d = dd(int)
    for i in range(2, int(n**0.5)+1):
        while n%i==0:
            d[i] += 1
            n //= i
        if not n:
            break
    if n>1:
        d[n] += 1
    return d

N = int(input())
d = dd(int)
for i in range(1, N+1):
    e = factorize(i)
    for i,j in e.items():
        d[i] += j

ans = 0
for i, j, k in p(d.values(), 3):    
    if i>=2 and j>=4 and k>=4:
        ans += 1
ans //= 2

for i, j in p(d.values(), 2):
    if i>=2 and j>=24:
        ans += 1
    if i>=4 and j>=14:
        ans += 1

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

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
pr=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
l=[0]*15
for i in range(1,N+1):
    for j in range(15):
        while 1:
            if i%pr[j]==0:
                i//=pr[j]
                l[j]+=1
            else:
                break
a,b,c,d,e=0,0,0,0,0
for i in l:
    if i>=2:
        a+=1
    if i>=4:
        b+=1
    if i>=14:
        c+=1
    if i>=24:
        d+=1
    if i>=74:
        e+=1
print((a-2)*b*(b-1)//2+c*(b-1)+d*(a-1)+e)

Submission status: Accepted

Solution code:
n = int(input())
primes = [0 for i in range(n+1)]
for i in range(2,n+1):
    cur = i
    for j in range(2,i+1):
        while cur % j == 0:
            cur = cur // j
            primes[j] += 1
def num(m):
    res = 0
    for i in primes:
        if i >= m-1:
            res += 1
    return res
print(num(75) + (num(5) - 1) * num(5) * (num(3) - 2) // 2
 + num(15) * (num(5) - 1) + num(25) * (num(3) - 1) )

Submission status: Accepted

Solution code:
from scipy.misc import comb

def prime_factorize_dict(N):
    d = dict()
    for n in range(2, N + 1):
        while not n & 1:
            d[2] = d.get(2, 0) + 1
            n >>= 1
        f = 3
        while f * f <= n:
            if not n % f:
                d[f] = d.get(f, 0) + 1
                n //= f
            else:
                f += 2
        if n != 1:
            d[n] = d.get(n, 0) + 1
    return {k:v for k, v in d.items() if v > 1}

d = prime_factorize_dict(int(input()))

l = [0] * 5
for p, k in d.items():
    if k < 4:
        index = 0
    elif k < 14:
        index = 1
    elif k < 24:
        index = 2
    elif k < 74:
        index = 3
    else:
        index = 4
    l[index] += 1

# 2, 4, 4
total = l[0] * comb(sum(l[1:]), 2, exact=True) + comb(sum(l[1:]), 3, exact=True) * 3
# 4, 14
total += l[1] * sum(l[2:]) + comb(sum(l[2:]), 2, exact=True) * 2
# 2, 24
total += sum(l[0:3]) * sum(l[3:]) + comb(sum(l[3:]), 2, exact=True) * 2
# 74
total += l[4]

print(total)

Submission status: Accepted

Solution code:
#114_D
N=int(input())
prime=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

def Count(x):
    res=0
    tmp=N
    while tmp//x:
        tmp=tmp//x
        res+=tmp
    return res

cnt=[Count(p) for p in prime]

def Sum(n):
    return sum([x>=n for x in cnt])

Ans=0
Ans=Sum(74)+Sum(24)*(Sum(2)-1)+Sum(14)*(Sum(4)-1)+Sum(4)*(Sum(4)-1)*(Sum(2)-2)//2
print(Ans)

Submission status: Accepted

Solution code:
n = int(input())

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

def f(x):
    return sum(exponent >= x - 1 for exponent in exponents)

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

print(ans)

Submission status: Accepted

Solution code:
import math
def C(a,b):
    if a < b:
        return 0
    else:
        return math.factorial(a) // (math.factorial(b)*math.factorial(a-b))

N = int(input())
if N == 1:
    print(0)

else:
    PF = dict()
    for i in range(2, N+1):
        n = i
        for x in PF.keys():
            while n % x == 0:
                n //= x
                PF[x] += 1
        if n != 1:
            PF[n] = 1
    
    count, number = [0]*5, [3, 5, 15, 25, 75]
    for x in PF.values():
        for i in range(5)[::-1]:
            if x + 1 >= number[i]:
                count[i] += 1
                break
    ans = 0
    ans += C(count[0], 1) * C(sum(count[1:]), 2) + 3 * C(sum(count[1:]), 3)
    ans += C(count[1], 1) * C(sum(count[2:]), 1) + 2 *C(sum(count[2:]), 2)
    ans += C(sum(count[:3]), 1) * C(sum(count[3:]), 1) + 2 * C(sum(count[3:]), 2)
    ans += count[4]
    print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())

prime = [0 for _ in range(47 + 1)]
lst = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

for i in range(2, N + 1):
	num = i
	# 素因数分解
	for p in lst:
		while True:
			if num % p == 0:
				num //= p
				prime[p] += 1
			else: break
			if num == 1: break
		

_75 = 0
_25 = 0
_15 = 0
_5 = 0
_3 = 0

for i in range(len(prime)):
	if prime[i] >= 2:
		_3 += 1
	if prime[i] >= 4:
		_5 += 1
	if prime[i] >= 14:
		_15 += 1
	if prime[i] >= 24:
		_25 += 1
	if prime[i] >= 74:
		_75 += 1
		
def comb(a, b):
	return math.factorial(a) / (math.factorial(b) * math.factorial(a - b))
		
ans = 0
ans += _75
ans += (_3 - 1) * _25 # かけられている数で1引いているのは、かける数で使っているものをかけられる数でも使う場合を除くため
ans += (_5 - 1) * _15
if _5 >= 2:
	ans += (_3 - 2) * comb(_5, 2)

print(int(ans))

Submission status: Accepted

Solution code:
def fac_count( x, counter):
    i=2;
    while x > 1:
        if x%i == 0:
            counter[i] = counter.get(i,0) + 1
            x //= i
        else:
            i += 1
    return counter

n=int(input())
counter = {}
for i in range(2,n+1):
    counter = fac_count(i,counter)

fac = [0] * 5 #2,4,14,24,74回以上

for i in counter.values():
    if i>=2:  fac[0] += 1
    if i>=4:  fac[1] += 1
    if i>=14: fac[2] += 1
    if i>=24: fac[3] += 1
    if i>=74: fac[4] += 1

 #3*5*5 / 3*25 / 5*15 / 75
ans =   fac[1] * (fac[1]-1)//2 * (fac[0]-2) + fac[3] * (fac[0] - 1) + fac[2] * (fac[1] - 1) + fac[4]
print(ans)

Submission status: Accepted

Solution code:
import bisect
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
def main():
    N = int(input())
    l = [0] * (N+1)
    for i in range(1, N+1):
        a = prime_factorize(i)
        for j in a:
            l[j] += 1
    l = l[2:]
    l.sort()
    r = 0
    a = bisect.bisect_left(l, 2)
    b = bisect.bisect_left(l, 4)
    c = bisect.bisect_left(l, 14)
    d = bisect.bisect_left(l, 24)
    e = bisect.bisect_left(l, 74)
    if e < N-1:
        r += N - e - 1
    if d < N-1:
        r += (N - d - 1) * (N - a - 2)
    if c < N-1:
        r += (N - c - 1) * (N - b - 2)
    if b < N-2:
        r += (N - a - 3) * (N - b - 1) * (N - b - 2) // 2
    print(r)
main()

Submission status: Accepted

Solution code:
def wareru(n,k):
    res = 0
    for i in range(1,n):
        plus = n//(k**i)
        res+= plus
        if plus == 0:break
    return res
n = int(input())
prime = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
a = []
for p in prime :
    if wareru(n,p) > 1:
        a.append(wareru(n,p))
    else:break
cnt = [0]*5
for num in a:
    if num >= 74:
        cnt[0]+=1
    if num >= 24:
        cnt[1] +=1
    if num >= 14:
        cnt[2] += 1
    if num >= 4:
        cnt[3] += 1
    cnt[4]+= 1
ans = cnt[0]
ans += cnt[1]*(cnt[4]-1)
ans += cnt[2]*(cnt[3]-1)
ans += cnt[3]*(cnt[3]-1)*(cnt[4]-2)//2
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from operator import mul

def fact_factors(n):
    f = []

    x = 2
    c = 0
    while x <= n:
        c += n // x
        x *= 2
    if c > 0:
        f.append((2, c))

    sv = [1] * (n + 1)
    lim = int(n**0.5) + 1
    for i in range(3, lim + 1, 2):
        if sv[i]:
            for j in range(i + i, n + 1, i):
                sv[j] = 0

    for i in range(3, n + 1, 2):
        if sv[i]:
            x = i
            c = 0
            while x <= n:
                c += n // x
                x *= i
            f.append((i, c))

    return f

import sys

def D(*a, **kwa):
    print(*a, file=sys.stderr, **kwa)

# 75 = 3 * 5**2
# 七五数 a**74, a**2 * b**24, a**4 * b**14, a**2 * b**4 * c**4
x_list_list = [[74], [24, 2], [14, 4], [4, 4, 2]]
div = [1, 1, 1, 2]

N = int(input())

f = fact_factors(N)
# D(f)

fx = [0] * (N+1)
afx = [0] * (N+1)
for f in fact_factors(N):
    fx[f[1]] += 1
for i in range(N, -1, -1):
    afx[i] = fx[i] if i == N else fx[i] + afx[i+1]
# D(fx)
# D(afx)

ans = 0
for i, x_list in enumerate(x_list_list):
    c = []
    for j, x in enumerate(x_list):
        if x > N:
            break
        c.append(afx[x]-j)
    if len(c):
        ans += reduce(mul, c) // div[i]

print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    def fact(x):
        r = []
        i = 0
        while x % 2 == 0:
            x //= 2
            i += 1
        if i:
            r.append((2, i))
        t = 3
        i = 0
        while t * t <= x:
            if x % t == 0:
                x //= t
                i += 1
            else:
                if i:
                    r.append((t, i))
                    i = 0
                t += 2
        if i:
            r.append((t, i))
        if x != 1:
            r.append((x, 1))
        return r
    f = {}
    for i in range(2, N + 1):
        for j, k in fact(i):
            f[j] = f.get(j, 0) + k
    f75, f25, f15, f5, f3 = 0, 0, 0, 0, 0
    for j, k in f.items():
        if k >= 74:
            f75 += 1
        if k >= 24:
            f25 += 1
        if k >= 14:
            f15 += 1
        if k >= 4:
            f5 += 1
        if k >= 2:
            f3 += 1
    return f75 + f25 * (f3 - 1) + f15 * (f5 - 1) + f5 * (f5 - 1) * (f3 - 2) // 2

print(main())

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc114/tasks/abc114_d

# 75数...約数をちょうど75個持つ整数
# 約数がちょうど75個→ その数を素因数分解すると
# A**74 or A**2 * B**4 * C**4 or A**2 * B**24 or A**16 * B**4 (必要条件？)

# N！の約数である→N!を割り切れる→素因数分解の肩の数が大きい

# N!の素因数分解の結果に対して、指数が4以上→2つ必要、2以上→1つ必要
# 一般化する。指数が4以上である底の個数をB,指数が2以上4未満である底の個数をAと定義した場合
# BC2 * A + BC3 が答えとなる


def factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 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


def make_divisors(n: int, sort=False):
    # 約数列挙
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    if sort:
        divisors.sort()
    return divisors


def combination_mod(n, r, mod):
    if r > n:
        return 0  # このような通りの数は無いため便宜上こう定義する
    r = min(r, n - r)
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
    return nf * pow(rf, mod - 2, mod) % mod


from collections import defaultdict

N = int(input())
fact = defaultdict(lambda: 0)
for n in range(1, N + 1):
    tmp = factorization(n)
    for k, v in tmp:
        fact[k] += v

# A**74 or B**2 * C**4 * D**4 or E**2 * F**24 or G**14 * H**4 (必要条件？)
A, B, C, D, E, F, G, H = 0, 0, 0, 0, 0, 0, 0, 0
for k, v in fact.items():
    if v >= 74:
        A += 1

    if v >= 4:
        C += 1
    if 2 <= v < 4:
        B += 1

    if v >= 24:
        F += 1
    if 24 > v >= 2:
        E += 1

    if v >= 14:
        G += 1
    if 14 > v >= 4:
        H += 1


# print(fact)
MOD = 10**9 + 7
ans = A
ans += combination_mod(C, 2, MOD) * B + combination_mod(C, 3, MOD) * 3
ans += E * F + combination_mod(F, 2, MOD) * 2
ans += G * H + combination_mod(G, 2, MOD) * 2

print(ans)

Submission status: Accepted

Solution code:

from collections import Counter
c = Counter()
N = int(input())


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

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

ans = 0
ans += num(75)
ans += (num(5) - 1) * num(15)
ans += (num(3) - 1) * num(25)
ans += (num(3) - 2) * num(5) * (num(5) - 1) // 2
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(500000)


def is_prime(n):
    import math
    if n == 1:
        return False

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

    return True


N = int(read())

primes = []

for i in range(1, N + 1):
    if is_prime(i):
        primes.append(i)

p_cnt = [0] * len(primes)

for i in range(1, N + 1):
    num = i
    for idx, p in enumerate(primes):
        while num % p == 0:
            p_cnt[idx] += 1
            num //= p
ans = 0
# p**74
for _, v in zip(primes, p_cnt):
    if v >= 74:
        ans += 1
# p**2, q**24 / p**4, q**14
for p, v in zip(primes, p_cnt):
    for q, v_ in zip(primes, p_cnt):
        if p == q:
            continue
        if v >= 2 and v_ >= 24:
            ans += 1
        if v >= 4 and v_ >= 14:
            ans += 1
# p **2, q ** 4, r ** 4
for p, v1 in zip(primes, p_cnt):
    for q, v2 in zip(primes, p_cnt):
        for r, v3 in zip(primes, p_cnt):
            if r <= q or p == q or r == p:
                continue
            if v1 >= 2 and v2 >= 4 and v3 >= 4:
                ans += 1

print(ans)

Submission status: Accepted

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

N=int(input())
from collections import defaultdict
dic=defaultdict(int)
for i in range(1,N+1):
  arr=factorization(i)
  for a in arr:
    dic[a[0]]+=a[1]
    
# これら素因数の集まりに対して、
# 2,4,4
# 74
# 2,24
# 4,14
# 個選択できるペアをいくつ作れるかを数える
items=dic.items()

def c(items,p):
  return len(list(filter(lambda x:x[1]>=p,items)))

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

Submission status: Accepted

Solution code:
N=int(input())
#75=3*5*5
#  =15*5
#  =3*25
#  =1*75

#N以下の素数
prime=[]
is_prime=[True]*(N+1)
is_prime[0]=is_prime[1]=False
for i in range(2,N+1):
    if is_prime[i]==False: continue
    prime.append(i)
    for j in range(i*i,N+1,i):
        is_prime[j]=False

#N!を素因数分解
import collections
pfac=collections.defaultdict(int)
for n in range(1,N+1):
    while n>1:
        for p in prime:
            if n%p==0:
                pfac[p]+=1
                n//=p

pfac2=sum([1 for n in pfac.values() if n>=2])
pfac4=sum([1 for n in pfac.values() if n>=4])
pfac14=sum([1 for n in pfac.values() if n>=14])
pfac24=sum([1 for n in pfac.values() if n>=24])
pfac74=sum([1 for n in pfac.values() if n>=74])

#3*5*5
ans=pfac4*(pfac4-1)*(pfac2-2)//2
#5*15
ans+=pfac14*(pfac4-1)
#3*25
ans+=pfac24*(pfac2-1)
#1*75
ans+=pfac74

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
e=[0]*(N+1)
for i in range(2,N+1):
    cur=i
    for j in range(2,i+1):
        while cur%j==0:
            e[j]+=1
            cur//=j
def 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:
# 10 -> [2,3,5,7]
def make_prime_list(k):
    p = [True] * (k+1)
    p[0] = False
    p[1] = False
    for i in range(2, k+1):
        if p[i]:
            for j in range(i*2, k+1, i):
                p[j] = False
    return [i for i in range(k + 1) if p[i]]


# 6 -> [[2,1],[3,1],[6,1]]
def get_prime_fact_dict(num):
    ps = make_prime_list(num//2)
    i = num
    prime_and_count = []

    for p in ps:
        count = 0
        while i % p == 0:
            i //= p
            count += 1
        if count > 0:
            prime_and_count.append([p, count])

    prime_and_count.append([num, 1])

    return prime_and_count


def solve(n):
    div_fact_count = [0] * (n+1)

    for i in range(2, n+1):
        xss = get_prime_fact_dict(i)
        for k, v in xss:
            div_fact_count[k] += v

    a = len([i for i in div_fact_count if i >= 74])
    b = len([i for i in div_fact_count if i >= 24])
    c = len([i for i in div_fact_count if i >= 14])
    d = len([i for i in div_fact_count if i >= 4])
    e = len([i for i in div_fact_count if i >= 2])

    # p**74
    c1 = a
    # p**24 * q**3
    c2 = b*(e-1)
    # p**14 ** q**4
    c3 = c * (d-1)
    # p**4 * q**4 * r*2
    # p and q are calculated as duplicated.
    c4 = (d * (d-1) * (e-2))//2

    return c1+c2+c3+c4


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

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())

def get_primes(lim):
    table = [True] * (lim+1)
    table[0:2] = False, False
    for i in range(2, int(lim**0.5)+1):
        if not table[i]: continue
        for j in range(i*2, lim+1, i):
            table[j] = False
    return [i for i in range(lim+1) if table[i]]

def factorize(x, primes):
    res = []
    for p in primes:
        if p ** 2 > x: break
        cnt = 0
        while not x % p:
            x //= p
            cnt += 1
        if cnt: res.append((p, cnt))
    if x > 1: res.append((x, 1))
    return res

p = get_primes(100)
ff = defaultdict(int)

for i in range(2, n+1):
    for x, num in factorize(i, p):
        ff[x] += num

ans = 0

for i in range(len(p)):
    if 74 <= ff[p[i]]: ans += 1
    for j in range(len(p)):
        if i == j: continue
        if 4 <= ff[p[i]] and 14 <= ff[p[j]]: ans += 1
        if 2 <= ff[p[i]] and 24 <= ff[p[j]]: ans += 1
        for k in range(j, len(p)):
            if j == k or i == k: continue
            if 2 <= ff[p[i]] and 4 <= ff[p[j]] and 4 <= ff[p[k]]:
                ans += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
div=[0]*(n+10)
for i in range(1,n+1):
  k=i
  for j in range(1,int(i**0.5)+1):
    cnt=0
    while k%(j+1)==0:
      k//=(j+1)
      cnt+=1
    div[j+1]+=cnt
  if k>1:
    div[k]+=1
ans=0
d=dict()
for i,j,k in [[4,4,2],[24,2,1000],[14,4,1000],[74,1000,1000]]:
  cnti,cntj,cntk=0,0,0
  for l in range(2,n+1):
    if j==1000 and k==1000:
      if div[l]>=i:
        ans+=1
    for m in range(2,n+1):
      if l!=m and j!=1000 and k==1000:
        if div[l]>=i and div[m]>=j:
            ans+=1
      for o in range(2,n+1):
        if (m,l) not in d:
          if l!=o and l!=m and m!=o:
            if i!=1000 and j!=1000 and k!=1000:
              if div[l]>=i and div[m]>=j and div[o]>=k:
                ans+=1
                d[(l,m)]=0
print(ans)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7
import math

def ddprint(x):
  if DBG:
    print(x)

def prime_division2(x):
    q = int(math.sqrt(x))
    h = {}
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            h[i] = ex
    if x>q:
        h[x] = 1
    return h

n = inn()
facc = {}
for i in range(1,n+1):
    f = prime_division2(i)
    ddprint("prdiv i {} f:".format(i))
    ddprint(f)
    for p in f:
        if p in facc:
            facc[p] += f[p]
        else:
            facc[p] = f[p]

ddprint(facc)
n74plus = len([x for x in facc if facc[x]>=74])
n24plus = len([x for x in facc if facc[x]>=24])
n14plus = len([x for x in facc if facc[x]>=14])
n4plus = len([x for x in facc if facc[x]>=4])
n2plus = len([x for x in facc if facc[x]>=2])
sm = n74plus
sm += n24plus*(n2plus-1)
sm += n14plus*(n4plus-1)
sm += n4plus*(n4plus-1)*(n2plus-2)//2
print(sm)

Submission status: Accepted

Solution code:
import math
import copy

def ord(N,n):#N,nは正の整数、Nで割り切れる回数、許容はN^1000
    if n%N!=0:
        return 0
    else:
        return 1+ord(N,n//N)

def primenubertable(N):#素数表　１００００ぐらいまでは時間内に計算できそう
    import math
    X=[1]*N
    X[0]=0
    X[1]=0
    i=2
    P=[]
    while math.sqrt(N)>=i:
        if X[i]==1:
            for j in range(i+1,N):
                if j%i==0:
                    X[j]=0
        i=i+1
    for i in range(0,N):
        if X[i]==1:
            P.append(i)
    return P

def factor(n):
    if n==0 or n==1:
        return 1
    else:
        return n*factor(n-1)

A=int(input())

N=factor(A)
P=primenubertable(100)
order=[]

for i in range(0,len(P)):
    x=ord(P[i],N)
    order.append(x)
a=0
b=0
c=0
d=0
e=0
for i in range(0,len(order)):
    if order[i]>=2:
        a=a+1
    if order[i]>=4:
        b=b+1
    if order[i]>=14:
        c=c+1
    if order[i]>=24:
        d=d+1
    if order[i]>=74:
        e=e+1
D=b*(b-1)//2
answer=D*(a-2)+c*(b-1)+d*(a-1)+e
print(answer)

Submission status: Accepted

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


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 count(n):
    t = {}
    while n != 1:
        for p in P:
            while n % p == 0:
                t[p] = t.setdefault(p, 0) + 1
                n //= p
    return t


def p_count(N):
    T = {}
    for n in range(1, N + 1):
        if n in P:
            T[n] = T.setdefault(n, 0) + 1
            continue
        
        t = count(n)
        for k, v in t.items():
            T[k] = T.setdefault(k, 0) + v
    return T


def main():
    N = int(input())
    T = p_count(N)
    L = sorted([t for t in T.keys() if T[t] >= 2])
    res = 0
    q = set()
    for i1, t1 in enumerate(L):
        for i2, t2 in enumerate(L[i1 + 1:]):
            for i3, t3 in enumerate(L[i1 + i2 + 2:]):
                if T[t2] >= 4 and T[t3] >= 4:
                    q.add((t1 ** 2) * (t2 ** 4) * (t3 ** 4))
                    res += 1
                if T[t1] >= 4 and T[t3] >= 4:
                    q.add(t1 ** 4 * t2 ** 2 * t3 ** 4)
                    res += 1
                if T[t1] >= 4 and T[t2] >= 4:
                    q.add(t1 ** 4 * t2 ** 4 * t3 ** 2)
                    res += 1

    for p, c1 in T.items():
        for q, c2 in T.items():
            if p == q:
                continue

            if c1 >= 2 and c2 >= 24:
                res += 1

            if c1 >= 4 and c2 >= 14:
                res += 1

    res += len([t for t in T.keys() if T[t] >= 74])

    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = [int(_) for _ in input().split()][0]

e = [0] * (N + 1)

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

dp = [[0] * 76 for _ in range(N + 1)]

dp[0][1] = 1
for i in range(1, N + 1):
    for j in range(e[i] + 1):  # i番目を j個使う
        for k in range(75 + 1):
            if k * (j + 1) > 75: break
            if dp[i - 1][k] > 0:
                dp[i][k * (j + 1)] += dp[i - 1][k]

# for i in range(len(dp)):
#     print(dp[i])
print(dp[N][75])

Submission status: Accepted

Solution code:
#とりまNまで素因数分解しておくか,dpか？

#nまでの素数を列挙
n = int(input())

#is_prime[i]にはi-1画素数か否かを示すboolが入る，[0]に1の素数判定がある．
is_prime = [True]*(n+1)
is_prime[0] = False

for i in range(2, n+1):
    if is_prime[i-1]:
        j = 2 * i
        while j <= n:
            is_prime[j-1] = False
            j += i

table = [ i for i in range(1, n+1) if is_prime[i-1]]

#素因数の個数リスト
hist=[0]*len(table)

#素因数分解して，histに追加
def p_fact(a):
    for i in range(len(table)):
        while a%table[i]==0:
            hist[i]+=1
            a=a//table[i]
            
for i in range(2,n+1):
    p_fact(i)

over2=0
over4=0#4個以上
over14=0
over24=0
over74=0
for i in range(len(hist)):
    if hist[i]>=2:
        over2+=1
        if hist[i]>=4:
            over4+=1
            if hist[i]>=14:
                over14+=1
                if hist[i]>=24:
                    over24+=1
                    if hist[i]>=74:
                        over74+=1
                    
        
ans=0
#素因数が(2,4,4)の組みを，素因数2のものから探す
for i in range(len(hist)):
    if hist[i]>=2:
        a=over4
        if hist[i]>=4:
            a-=1
        ans+=(a*(a-1))//2
        
    if hist[i]>=14:#素因数が(4,14)の組みは，素因数が14のものから探す
        ans+=over4-1
    
    if hist[i]>=24:
        ans+=over2-1

if over74==1:
    ans+=1
        
print(ans)

Submission status: Accepted

Solution code:
N = int(input()) 
e=[0]*(N+1)
for i in range(2, N+1):
    cur = i
    for j in range(2, i+1):
        while cur % j == 0:
            e[j] += 1
            cur //= j
def 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)