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

prime=[]
for n in range(2, N+1):
    for i in range(2, n):
        if n % i == 0:
            break
    else:
        prime.append(n)
#print(prime)

bucket=[0]*(N+1)
for i in range(2, N+1):
    for p in prime:
        while i % p == 0:
            i //= p
            bucket[p] += 1
#print(bucket)

cnt = 0
for i in range(2, N+1):
    if bucket[i] >= 74:
        cnt += 1
    if bucket[i] >= 24:
        cnt += len([bucket[j] for j in range(2, N+1) \
             if j != i and bucket[j] >= 2])
    if bucket[i] >= 14:
        cnt += len([bucket[j] for j in range(2, N + 1) \
                    if j != i and bucket[j] >= 4])
    if bucket[i] >= 4:
        for j in range(i+1, N+1):
            if j != i:
                if bucket[j] >= 4:
                    #print(i,j)
                    cnt += len([bucket[k] for k in range(2, N + 1)\
                    if k != i and k != j and bucket[k] >= 2])
print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
D=[0]*(N+1)
for i in range(2,N+1):
  a=i
  for j in range(2,i+1):
    while a%j==0:
      D[j]+=1
      a//=j
def num(x):
  cnt=0
  for i in D:
    if i>=x-1:
      cnt+=1
  return cnt

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

Submission status: Accepted

Solution code:
from collections import defaultdict

def dfs(i, c):
    key = (i, c)
    if key in memo:
        return memo[key]
    if c == 75:
        return 1
    if i == m:
        return 0
    k, v = p[i]
    r = 0
    for j in range(v + 1):
        if c * (j + 1) <= 75:
            r += dfs(i + 1, c * (j + 1))
    memo[key] = r
    return r

n = int(input())
index = defaultdict(int)

for x in range(2, n + 1):
    y = 2
    while y ** 2 <= x:
        while x % y == 0:
            x //= y
            index[y] += 1
        y += 1
    if x > 1:
        index[x] += 1

*p, = index.items()
m = len(p)
memo = {}

print(dfs(0, 1))

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)))

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import Counter


def prime_factorization(divs, n):
    while n % 2 == 0:
        divs[2] += 1
        n //= 2

    i = 3
    while i <= int(n ** .5) + 1:
        while n % i == 0:
            divs[i] += 1
            n //= i
        i += 2
    if n != 1:
        divs[n] += 1

    return divs


def num(m):
    return sum([value if key >= m else 0 for key, value in cnt_divs.items()])


N = int(input())
divs = defaultdict(int)
for n in range(2, N + 1):
    divs = prime_factorization(divs, n)

cnt_divs = Counter(divs.values())

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

Submission status: Accepted

Solution code:
n = int(input())

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

d.sort()
d1 = [i for i in d if i >=2]

def num(m): # e の要素のうち m-1 以上のものの個数
    return len(list(filter(lambda x: x >= m-1, d1)))

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

Submission status: Accepted

Solution code:
n=int(input())
cnt=[0]*(n+1)
s=set([2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,91,97])
for k in range(1,n+1):
  for i in range(2,k+1):
    if k%i==0 and i in s:
      m=k
      while m%i==0:
        cnt[i]+=1
        m//=i
cnt2,cnt4,cnt14,cnt24,cnt74=0,0,0,0,0
for i in range(2,n+1):
  if cnt[i]>=2:
    cnt2+=1
  if cnt[i]>=4:
    cnt4+=1
  if cnt[i]>=14:
    cnt14+=1
  if cnt[i]>=24:
    cnt24+=1
  if cnt[i]>=74:
    cnt74+=1
ans=cnt74+cnt14*(cnt4-1)+cnt24*(cnt2-1)+(cnt2-2)*cnt4*(cnt4-1)//2
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): # e の要素のうち m-1 以上のものの個数
    return len(list(filter(lambda x: x >= m-1, e)))

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

Submission status: Accepted

Solution code:
from collections import Counter
from operator import mul
from functools import reduce
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())
    factors = [1]
    for i in range(1, N+1):
        factors += prime_factorize(i)
    cnt = Counter(factors)
    cntlst = list(cnt.values())
    
    count74 = sum([1 for val in cntlst if val>=74])
    count24 = sum([1 for val in cntlst if val>=24])
    count14 = sum([1 for val in cntlst if val>=14])
    count4  = sum([1 for val in cntlst if val>=4])
    count2  = sum([1 for val in cntlst if val>=2])
    
    ans = count74 + count24*(count2-1) + count14*(count4-1) \
                + (count4*(count4-1)*(count2-2))//2
    print(ans)

main()

Submission status: Accepted

Solution code:
n = int(input())

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

import math
def div(m):
  d = {}
  temp = int(math.sqrt(m))+1
  for i in range(2, temp):
    while m%i== 0:
      m //= i
      if i in d:
        d[i] += 1
      else:
        d[i] = 1
  if d == {}:
    d[m] = 1
  else:
    if m in d:
      d[m] += 1
    elif m != 1:
      d[m] =1
  return d

D = {}
for i in range(2, n+1):
    d = div(i)
    for k, v in d.items():
        if k in D:
            D[k] += v
        else:
            D[k] = v
#print(D)

A = set()
B = set()
P = set()
Q = set()
R = set()
for k, v in D.items():
    if v >= 74:
        R.add(k)
    if v >= 24:
        P.add(k)
    if v >= 14:
        Q.add(k)
    if v >= 4:
        B.add(k)
    if v >= 2:
        A.add(k)

ans = 0
b = len(B)
for a in A:
    if a not in B:
        ans += b*(b-1)//2
    else:
        ans += (b-1)*(b-2)//2

p = len(P)
for a in A:
    if  a not in P:
        ans += p
    else:
        ans += p-1

q = len(Q)
for b in B:
    if b not in Q:
        ans += q
    else:
        ans += q-1

ans += len(R)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = [0] * 100
c74, c24, c14, c4, c2 = 0, 0, 0, 0, 0
for i in range(2, N + 1):
    a = i
    for j in range(2, i + 1):
        while a % j == 0:
            a //= j 
            S[j] += 1
            if S[j] == 74:
                c74 += 1
            if S[j] == 24:
                c24 += 1
            if S[j] == 14:
                c14 += 1
            if S[j] == 4:
                c4 += 1
            if S[j] == 2:
                c2 += 1
        if a == 1:
            break
ans = c74 + c24 * (c2 - 1) + c14 * (c4 - 1) + c4 * (c4 - 1) * (c2 - 2)  // 2
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

from collections import defaultdict

d = defaultdict(int)

for i in range(2, n + 1):
    arr = factorization(i)
    for j in arr:
        d[j[0]] += j[1]
v = d.values()

from collections import Counter

c = Counter(v)
li = [0]*5

for i in c.keys():
    if i >= 2:
        li[0] += c[i] # 2
    if i >= 4:
        li[1] += c[i] # 4
    if i >= 14:
        li[2] += c[i] # 14
    if i >= 24:
        li[3] += c[i] # 24
    if i >= 74:
        li[4] += c[i] # 74

ans = 0
ans += li[1] * (li[1] - 1) // 2 * (li[0] - 2)
ans += li[2] * (li[1] - 1)
ans += li[3] * (li[0] - 1)
ans += li[4]

print(ans)

Submission status: Accepted

Solution code:
def c(n, P):
    return sum([1 for p in P if p + 1 >= n])


N = int(input())
pN = {}
for i in range(N + 1):
    for j in range(2, i + 1):
        while i % j == 0:
            i //= j
            pN[j] = pN.get(j, 0) + 1
V = pN.values()
ans = c(75, V)
ans += c(25, V) * (c(3, V) - 1)
ans += c(15, V) * (c(5, V) - 1)
ans += c(5, V) * (c(5, V) - 1) * (c(3, V) - 2) // 2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import itertools
import math
def prime(n):
    ma=int(math.sqrt(n))+1
    li=[i for i in range(2,n+1)]
    primes=[]
    while li[0]<=ma:
        primes.append(li[0])
        tmp=li[0]
        li=[i for i in li if i%tmp!=0]
    primes.extend(li)
    return primes

n=int(input())
if(n<10):
    print(0)
    exit()
primes=prime(n+1)
factor=[]
for i in range(2,n+1):
    tmp=i
    for k in primes:
        while(tmp%k==0):
            tmp//=k
            factor.append(k)
values,counts=zip(*Counter(factor).most_common())
counts=list(counts)
ans=0
for i in counts:
    if(i>=74):
        ans+=1
for k in itertools.combinations(counts,2):
    if(k[0]>=2 and k[1]>=24):
        ans+=1
    if(k[0]>=4 and k[1]>=14):
        ans+=1
    if(k[0]>=24 and k[1]>=2):
        ans+=1
    if(k[0]>=14 and k[1]>=4):
        ans+=1
for k in itertools.combinations(counts,3):
    if(k[0]>=2 and k[1]>=4 and k[2]>=4):
        ans+=1
    if(k[1]>=2 and k[2]>=4 and k[0]>=4):
        ans+=1
    if(k[2]>=2 and k[1]>=4 and k[0]>=4):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:

n = int(input())

div_cnt = [0] * n

def search_div(data, n):
    while n != 1:
        for i in range(2, n + 1):
            if n % i == 0:
                data[i - 1] += 1
                n = int(n / i)
                break
        

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

def count_num(data, n):
    cnt = 0
    for i in range(len(data)):
        if data[i] >= n - 1:
            cnt += 1
    
    return cnt
print(int(count_num(div_cnt, 75) + count_num(div_cnt, 25) * (count_num(div_cnt, 3) - 1) + count_num(div_cnt, 15) * (count_num(div_cnt, 5) - 1) + count_num(div_cnt, 5) * (count_num(div_cnt, 5) - 1) / 2 * (count_num(div_cnt, 3) - 2)))

Submission status: Accepted

Solution code:

n = int(input())

div_cnt = [0] * n

def search_div(data, n):
    while n != 1:
        for i in range(2, n + 1):
            if n % i == 0:
                data[i - 1] += 1
                n = int(n / i)
                break
        

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

cnt_2 = 0
cnt_4 = 0
cnt_14 = 0
cnt_24 = 0
cnt_74 = 0
if max(div_cnt) < 4:
    print(0)
    exit()

for i in range(n):
    if div_cnt[i] >= 74:
        cnt_2 += 1
        cnt_4 += 1
        cnt_14 += 1
        cnt_24 += 1
        cnt_74 += 1
    elif div_cnt[i] >= 24:
        cnt_2 += 1
        cnt_4 += 1
        cnt_14 += 1
        cnt_24 += 1
    elif div_cnt[i] >= 14:
        cnt_2 += 1
        cnt_4 += 1
        cnt_14 += 1
    elif div_cnt[i] >= 4:
        cnt_2 += 1
        cnt_4 += 1
    elif div_cnt[i] >= 2:
        cnt_2 += 1
    
ans = cnt_74 + cnt_24 * (cnt_2 - 1) + cnt_14 * (cnt_4 - 1) + (cnt_4 * (cnt_4 - 1)) / 2 * (cnt_2 - 2)
print(int(ans))

Submission status: Accepted

Solution code:
# なぜかうまくいかない
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_right, bisect_left

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

e = [0] * (N + 1)

for i in range(2, N + 1):
    cur = i
    for j in range(2, N + 1):
        while cur % j == 0:
            # 割り切れるなら，割り切れるjの数を数える
            e[j] += 1
            cur //= j
def num(m):
    return len(list(filter (lambda x: x >= m - 1, e)))

ans = num(75) + num(25) * (num(3) - 1) + num(15) * (num(5) - 1) + num(5) * (num(5) - 1) * (num(3) - 2) // 2
print(ans)
# for n in range(1, N+1):
#     prime = prime_decomposition(n)
#     print(prime)
#     for p in prime:
#         p = int(p)
#         prime_num[p] += 1
# print(prime_num)
# num = [0] * 81
# for p_num in prime_num:
#     # if p_num <= 80:
#     p_num = min(80, p_num)
#     for i in range(1, p_num+1):
#         num[i] += 1
# print(num)
# # 同じ素数は取らないように
# ans = num[75] + num[25] * (num[3] - 1) + num[15] * (num[5] - 1) + num[5] * (num[5] - 1) * (num[3] - 2) // 2
# print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

def fctr1(n): 
    f = []
    for i in range(2,int(n**0.5)+2):
        while n%i == 0:
            n = n//i
            f.append(i)
    if n != 1:
        f.append(n)
    return f


n = int(input())

p_list = []
for i in range(1,n+1):
    p_list = p_list + fctr1(i)

pc = Counter(p_list).most_common()

#print(pc)

c74 = 0
c24 = 0
c14 = 0
c4 = 0
c2 = 0

for i in range(len(pc)):
    if pc[i][1] >= 74:
        c74 += 1
    if pc[i][1] >= 24:
        c24 += 1
    if pc[i][1] >= 14:
        c14 += 1
    if pc[i][1] >= 4:
        c4 += 1
    if pc[i][1] >= 2:
        c2 += 1

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

print(ans)

Submission status: Accepted

Solution code:
# 入力
N = int(input())

# pfacから次数がn以上の素数の数を返す
def p_deg_le(pfac, n):
    ret = 0
    for p_deg in pfac:
        if p_deg[1] >= n: ret += 1
        else: break
    return ret


# 100までの素数
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!を素因数分解
pfac = {} # N!の素因数分解
for i in range(1, N + 1):
    for p in P:
        while i % p == 0:
            if p in pfac:   pfac[p] += 1
            else:           pfac[p] = 1
            i //= p

# 次数の多い素数が前にくるようソート
pfac = sorted(pfac.items(), reverse = True, key = lambda x : x[1])

fact = 1
for p_deg in pfac:
    fact *= p_deg[0] ** p_deg[1]


# 約数が75 = 3 * 5 * 5個あるN!の約数は以下のいずれかの形のq
# q = p1^74, q = p1^24 * p2^2, q = p1^14 * p2^4,
# q = p1^4 * p2^4 * p3^2
p_deg = {}
for deg in (2, 4, 14, 24, 74):
    p_deg[deg] = p_deg_le(pfac, deg)

# q = p1^4 * p2^4 * p3^2
ans = (p_deg[4] * (p_deg[4] - 1) // 2) * (p_deg[2] - 2)
# q = p1^14 * p2^4
ans += p_deg[14] * (p_deg[4] - 1)
# q = p1^24 * p2^2
ans += p_deg[24] * (p_deg[2] - 1)
# q = p1^74
ans += p_deg[74]

print(ans)

Submission status: Accepted

Solution code:
n=int(input())

N=[0]*(n+1)

def f(n):
    M=[]
    while n%2==0:
        n//=2
        M.append(2)
    i=3
    while n>=i:
        while n%i==0:
            n//=i
            M.append(i)
        i+=2
    return M

for i in range(2,n+1):
    for j in f(i):
        N[j]+=1

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

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

Submission status: Accepted

Solution code:
n=int(input())

N=[0]*(n+1)

def f(n):
    M=[]
    while n%2==0:
        n//=2
        M.append(2)
    i=3
    while n>=i:
        while n%i==0:
            n//=i
            M.append(i)
        i+=2
    return M

for i in range(2,n+1):
    for j in f(i):
        N[j]+=1

ANS=[0]*5

for i in range(1,n+1):
    if N[i]>=74:
        ANS[0]+=1
    elif N[i]>=24:
        ANS[1]+=1
    elif N[i]>=14:
        ANS[2]+=1
    elif N[i]>=4:
        ANS[3]+=1
    elif N[i]>=2:
        ANS[4]+=1

ANS[1]+=ANS[0]
ANS[2]+=ANS[1]
ANS[3]+=ANS[2]
ANS[4]+=ANS[3]

print(ANS[0]+ANS[1]*(ANS[4]-1)+ANS[2]*(ANS[3]-1)+(ANS[3]*(ANS[3]-1)//2)*(ANS[4]-2))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from collections import defaultdict

N = int(input())

if N < 10:
    print(0)
    exit()


d = defaultdict(list)
d[2]=7
d[3]=4
d[5]=1
d[7]=1

#nの素因数分解(O(n**0.5)
def prime_factor(n):
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            if d[i] == []: d[i]=1
            else: d[i] += 1
            n = n//i
    if n != 1:
        if d[n] == []: d[n]=1
        else: d[n] += 1

for i in range(10,N+1):
    prime_factor(i)

cand2 = 0
cand4 = 0
cand14 = 0
cand24 = 0
cand74 = 0

for key,val in d.items():
    if val >= 2:
        cand2 += 1
        if val >=4:
            cand4 += 1
            if val >=14:
                cand14 += 1
                if val >=24:
                    cand24 += 1
                    if val >=74:
                        cand74 += 1


ans = 0
ans += cand4  * (cand4-1)//2 * (cand2-2)
ans += cand24 * (cand2-1)
ans += cand14 * (cand4-1)
ans += cand74

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

from math import factorial
def comb(n, r):
    if n < r:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)

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

d = {}

for i in range(1, n+1):
    for m, cnt in factorization(i):
        if m == 1:
            continue
        if m in d:
            d[m] += cnt
        else:
            d[m] = cnt

cnt = [0 for i in range(100)]

for k in d:
    cnt[d[k]] += 1

print(
    sum(cnt[74:]) + # 75
    sum(cnt[4:14]) * sum(cnt[14:]) + sum(cnt[14:]) * (sum(cnt[14:])-1) + # 5 * 15
    sum(cnt[2:24]) * sum(cnt[24:]) + sum(cnt[24:]) * (sum(cnt[24:])-1) + # 3 * 25
    sum(cnt[2:4]) * comb(sum(cnt[4:]), 2) + sum(cnt[4:]) * comb(sum(cnt[4:])-1, 2) # 3 * 5 * 5
)

Submission status: Accepted

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

N = int(input().strip())
#-----


class factorization():
    def get_divisor(self, n :int) -> dict:
        divisor_dic={}
        
        tmp_num = n
        for i in range(2,n):
            while tmp_num % i == 0:
                divisor_dic.setdefault(i,0)
                divisor_dic[i] += 1
                
                tmp_num //= i
        
        return divisor_dic


divisor_dic={}  # 階乗を素因数分解し、結果を入れる
for num in range(2,N+1):
    # 階乗の、それぞれの数字について、約数を抽出
    fa = factorization()
    ret = fa.get_divisor(num)

    for key,v in ret.items():
        divisor_dic.setdefault(key,0)
        divisor_dic[key] += v
    
    divisor_dic.setdefault(num,0)
    divisor_dic[num] += 1


cnt_divisor_dic={ i:0 for i in [74,24,14,4,2]}
# 約数の個数が74以上、24,14,4,2以上、で場合分けし、件数を集計
for key,v in divisor_dic.items():
    for j in [74,24,14,4,2]:
        if v >= j:
            cnt_divisor_dic[j] += 1


# 75=5*5*3　をもとに、すべての組み合わせを考え、合計する。
# 75
# 25 × 3(選択した「25以上」の約数は、「3以上」の約数でもあるため、1引いておく)
# 15 × 5(選択した「15以上」の約数は、「5以上」の約数でもあるため、1引いておく)
# 5×5×3 (「5以上」の約数から2つ選択する組み合わせxC2)
sum = cnt_divisor_dic[74] + \
      cnt_divisor_dic[24] * (cnt_divisor_dic[2] - 1) + \
      cnt_divisor_dic[14] * (cnt_divisor_dic[4] - 1) + \
      cnt_divisor_dic[4] * (cnt_divisor_dic[4] - 1) // (2*1) * (cnt_divisor_dic[2] - 2)

print(sum)

Submission status: Accepted

Solution code:
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

primes = primes(100)

N = int(input())

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

# eの要素で(M - 1)以上のものの個数
cnt = lambda M: len(tuple(filter(lambda x: x >= M - 1, e)))

ans = cnt(75) # 75
ans += cnt(25) * (cnt(3) - 1) # 25 * 3 = 75
ans += cnt(15) * (cnt(5) - 1) # 15 * 5 = 75
# 「// 2」は2つのcnt(5)は区別しないから
ans += cnt(5) * (cnt(5) - 1) * (cnt(3) - 2) // 2 # 5 * 5 * 3 = 75

print(ans)

Submission status: Accepted

Solution code:
def the_sieve_of_eratosthenes(i):
    s = [j for j in range(2, i + 1)]
    j = 0
    while True:
        if j >= i - 3:
            for k in range(len(s) - 1, 0, -1):
                if s[k] == 0:
                    del s[k]
            return s
        if s[j] != 0:
            for k in range(2 * s[j] - 2, i - 1, s[j]):
                s[k] = 0
        j += 1

n = int(input())
p = the_sieve_of_eratosthenes(n)
c = [1] * len(p)
for i in range(2, n + 1):
    if not i in p:
        j = 0
        while True:
            if i == 1 or j == len(p):
                break
            if i % p[j] == 0:
                i /= p[j]
                c[j] += 1
            else:
                j += 1
a1, a2, a3, a4, a5 = 0, 0, 0, 0, 0
ans = 0
for i in c:
    if i >= 2:
        a1 += 1
    if i >= 4:
        a2 += 1
    if i >= 14:
        a3 += 1
    if i >= 24:
        a4 += 1
    if i >= 74:
        a5 += 1
ans = ((a1 - 2) * a2 * (a2 - 1) // 2) + (a2 - 1) * a3 + (a1 - 1) * a4 + a5
print(ans)

Submission status: Accepted

Solution code:
x=[]

for j in range(100):
    m=j+1
    pf={}
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:pf[m]=1
    x.append(pf)

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

from collections import defaultdict
d=defaultdict(int)
for i in range(1,N):
    for k in x[i].keys():
        d[k]+=x[i][k]

#print(d)
over2=0
over4=0
over14=0
over24=0
over74=0
for k in d.keys():
    if d[k]>=2:
        over2+=1
    if d[k]>=4:
        over4+=1
    if d[k]>=14:
        over14+=1
    if d[k]>=24:
        over24+=1
    if d[k]>=74:
        over74+=1

ans=0
#case1
ans+=over4*(over4-1)//2*(over2-2)
#case2
ans+=over14*(over4-1)
#case3
ans+=over24*(over2-1)
#case4
ans+=over74
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def factorization(n):
    if n == 1: return []
    res = []
    x = n
    y = 2
    while y * y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1: res.append(x)
    return res

N = int(input())

D = defaultdict(int)

for i in range(1, N + 1):
    F = factorization(i)
    for f in F:
        D[f] += 1

cnt_75 = 0
cnt_25 = 0
cnt_15 = 0
cnt_5 = 0
cnt_3 = 0

for v in D.values():
    if v + 1 >= 75:
        cnt_75 += 1
    if v + 1 >= 25:
        cnt_25 += 1
    if v + 1 >= 15:
        cnt_15 += 1
    if v + 1 >= 5:
        cnt_5 += 1
    if v + 1 >= 3:
        cnt_3 += 1

ans = 0

ans += cnt_75
ans += cnt_25 * (cnt_3 - 1)
ans += cnt_15 * (cnt_5 - 1)
ans += cnt_5 * (cnt_5 - 1) // 2  * (cnt_3 - 2)

print(ans)

Submission status: Accepted

Solution code:
def factorization(n):
    d = {}
    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
            d[i] = cnt
    if temp!=1:
        d[temp] = 1
    if len(d) == 0:
        d[n] = 1
    return d

N = int(input())
fac_dict = {}
for n in range(1, N+1):
  d = factorization(n)
  for p in d:
    if p in fac_dict:
      fac_dict[p] += d[p]
    else:
      fac_dict[p] = d[p]

# [74個以上, 24個以上, 14個以上, 4個以上, 2個以上]
num_prime = [0, 0, 0, 0, 0]
for p in fac_dict:
  num = fac_dict[p]
  if num >= 2:
    num_prime[4] += 1
    if num >= 4:
      num_prime[3] += 1
      if num >= 14:
        num_prime[2] += 1
        if num >= 24:
          num_prime[1] += 1
          if num >= 74:
            num_prime[0] += 1

ans = 0
ans += num_prime[0] # A = p**74 のパターン
ans += num_prime[1] * (num_prime[4]-1) # A = p1**2 * p2**24 のパターン
ans += num_prime[2] * (num_prime[3]-1) # A = p1**4 * p2**14 のパターン
ans += (num_prime[3]*(num_prime[3]-1)//2) * (num_prime[4]-2) # A = p1**2 * p2**4 * p3**4 のパターン
print(ans)

Submission status: Accepted

Solution code:
# 解説AC
# 約数75になる条件は、素因数分解した際の約数の数p, q,..について
# (p+1)*(q+1)*..=75となること
# 先に上式を満たす(p,q, ..)組み合わせを列挙して、
# N!の素因数分解に対して、各組み合わせを満たすものを数え上げる

n = int(input())

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

Primes_count = [0 for _ in range(n+1)]

for i in range(2,n+1):
    Primes = prime_factorization(i)
    for prime in Primes:
        Primes_count[prime] += 1

# 75 = 3*5*5 = (1*75) = (3*25) = (3*5*5) = (5*15)
def count(n, Primes_count):
    return len(list(filter(lambda x:x>=n-1, Primes_count)))

ans = 0
# 1*75
ans += count(75, Primes_count)

# 3*25 3に対する-1は25以上とのかぶりを避けるため。
ans += (count(3, Primes_count)-1) * count(25, Primes_count)

# 5*15 上と同様
ans += (count(5, Primes_count)-1) * count(15, Primes_count)

# 3*5*5 5以上を一つ決める->残りから5以上を一つ決める->残りから3以上を1つ決める->5同士の入れ替えが起きるので2で割り切り捨てる
ans += (count(5, Primes_count)) * (count(5, Primes_count) -1) * (count(3, Primes_count)-2) // 2

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
c = [0 for i in range(101)]

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

for i in range(2,N+1):
    factors = prime_factorize(i)
    for factor in factors:
        c[factor] += 1
c = [e+1 for e in c]

ans = 0
#75 = 5*5*3
more75 = len(list(filter(lambda x:x>=75,c)))
more25 = len(list(filter(lambda x:x>=25,c)))
more15 = len(list(filter(lambda x:x>=15,c)))
more5 = len(list(filter(lambda x:x>=5,c)))
more3 = len(list(filter(lambda x:x>=3,c)))

ans += more75
if more25:
    ans += more25*(more3-1)
if more15:
    ans += more15*(more5-1)
if more5 >= 2 and more3 >= 3:
    ans += (more3-2)*(more5*(more5-1))//2
print(ans)

Submission status: Accepted

Solution code:
def sieve(n):
    prime=[]
    limit=n**0.5
    data=[i+1 for i in range(1,n)]
    while True:
        p=data[0]
        if limit<=p:
            return prime+data
        prime.append(p)
        data=[e for e in data if e%p!=0]

def main():
    n=int(input())
    primes=sieve(n+1)
    l=len(primes)

    factor=[]
    for i in range(l):
        p = primes[i]
        cnt = 0
        fac = p
        while fac <= n:
            cnt += n//fac
            fac *= p
        factor.append(cnt)
    
    l2=len(factor)
    idx=[0,0,0,0,0]
    fac=[2,4,14,24,74]
    j,i=4,0
    while i<l2:
        if  factor[i] < fac[j]:
            idx[j] = i
            j-=1
            if j==-1:
                break
        else:
            i+=1

    ans=idx[4]+idx[3]*max(0,idx[0]-1)+idx[2]*max(0,idx[1]-1)+idx[1]*max(0,idx[1]-1)*max(0,idx[0]-2)//2
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

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

def check_div_n(div_list, n):
  return len([d for d in div_list if d>=n and d!=0])

for i in range(2, n+1):
  check_n = i
  for j in range(2, n+1):
    while check_n%j==0:
      D[j] += 1
      check_n = check_n//j
      
ans = check_div_n(D, 74) + \
      (check_div_n(D, 4)-1)*check_div_n(D, 14) + \
      (check_div_n(D, 2)-1)*check_div_n(D, 24) + \
      check_div_n(D, 4)*(check_div_n(D, 4)-1)//2 * \
      (check_div_n(D, 2)-2)
  
print(ans)

Submission status: Accepted

Solution code:
import math
n=int(input())
#generate all the primes 
def chk_prime(n):
  for i in range(2,int(math.sqrt(n))+1):
    if n%i==0:
      return False
  return True
primes=[]
for i in range(2,n+1):
  if chk_prime(i):
    primes.append(i)
cc=[0]*len(primes)
for i in range(2,n+1):
  num=i
  for j in range(len(primes)):
    cnt=0
    while num%primes[j]==0:
      num//=primes[j]
      cnt+=1
    cc[j]+=cnt
ans=0
#count how many are of the type 75
for i in cc:
  if i>=74:
    ans+=1
#count how many are of the type 25,3
cnt_24=0
cnt_2=0
for i in cc:
  if i>=24:
    cnt_24+=1
  if i>=2:
    cnt_2+=1
ans+=cnt_24*(cnt_2-1)
#count how many are of the type 15,5
cnt_14=0
cnt_4=0
for i in cc:
  if i>=14:
    cnt_14+=1
  if i>=4:
    cnt_4+=1
ans+=cnt_14*(cnt_4-1)
#count how many are of the type 5,5,3
cnt_4=0
for i in cc:
  if i>=4:
    cnt_4+=1
ans+=((cnt_4*(cnt_4-1))//2)*(cnt_2-2)
print(ans)

Submission status: Accepted

Solution code:
def sieve(n):
    prime = [True] * (n+1)
    prime[0] = prime[1] = False
    count = 0
    for i in range(2, n+1):
        if prime[i]:
            count += 1
            for j in range(2*i, n+1, i):
                prime[j] = False
    return prime


def count(p):
    cnt = 0
    n = N
    while n > 0:
        n //= p
        cnt += n
    return cnt


N = int(input())
prime = sieve(N)
ans = 0

# case 1: p^74
for p in range(N+1):
    if not prime[p]:
        continue
    if count(p) < 74:
        break
    ans += 1

# case 2: p^2 q^4 r^4
for p in range(N+1):
    if not prime[p]:
        continue
    if count(p) < 2:
        break
    for q in range(N):
        if not prime[q] or p == q:
            continue
        if count(q) < 4:
            break
        for r in range(q+1, N+1):
            if not prime[r] or p == r:
                continue
            if count(r) < 4:
                break
            ans += 1

# case 3: p^4 q^14
for p in range(N+1):
    if not prime[p]:
        continue
    if count(p) < 4:
        break
    for q in range(N+1):
        if not prime[q] or p == q:
            continue
        if count(q) < 14:
            break
        ans += 1

# case 3: p^2 q^24
for p in range(N+1):
    if not prime[p]:
        continue
    if count(p) < 2:
        break
    for q in range(N+1):
        if not prime[q] or p == q:
            continue
        if count(q) < 24:
            break
        ans += 1

print(ans)