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:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def make_divisors(n):
    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)

    return divisors

def prime_factorization(n, res):
    for i in range(2, int(pow(n, 0.5))+1):
        if n % i: continue
        ex = 0
        while n % i == 0:
            n = n // i
            ex += 1
        res[i] = res.get(i, 0) + ex
    if n != 1:
        res[n] = res.get(n, 0) + 1
    return res

def solve():
    N = II()

    # print(make_divisors(120))
    memo = {}
    for i in range(1, N+1):
        memo = prime_factorization(i, memo)

    # print(memo)

    def e(num):
        res = 0
        for v in memo.values():
            if v >= num:
               res += 1
        return res

    ans = 0
    # 2 * 4 * 4
    ans += e(4) * (e(4) - 1) * (e(2) - 2) // 2


    # 4 * 14
    ans += (e(4) - 1) * e(14)

    # 2 * 24
    ans += (e(2) - 1) * e(24)

    # 74
    ans += e(74)

    print(ans)



if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def prime_factorize(N): #素因数分解
    exponent = 0
    while N%2 == 0:
        exponent += 1
        N //= 2
    if exponent: factorization = [[2,exponent]]
    else: factorization = []
    i=1
    while i*i <=N:
        i += 2
        if N%i: continue
        exponent = 0
        while N%i == 0:
            exponent += 1
            N //= i
        factorization.append([i,exponent])
    if N!= 1: factorization.append([N,1])
    assert N != 0, "zero"
    return factorization

N = int(input())
factor = [0]*101

for i in range(1,N+1):
    f = prime_factorize(i)
    for p,n in f:
        factor[p] += n

ov2 = 0
ov4 = 0
ov14 = 0
ov24 = 0
ov74 = 0
for f in factor:
    if 2 <= f:
        ov2 += 1
    if 4 <= f:
        ov4 += 1
    if 14 <= f:
        ov14 += 1
    if 24 <= f:
        ov24 += 1
    if 74 <= f:
        ov74 += 1

ans = 0
##(2,4,4)
ans += (ov2-ov4)*(ov4)*(ov4-1)//2 + ov4*(ov4-1)*(ov4-2)//2

##(2,24)
ans += (ov2-ov24)*(ov24) + (ov24-1)*(ov24)

##(14,4)
ans += (ov4-ov14)*(ov14) + (ov14-1)*(ov14)

##(74)
ans += ov74

print(ans)

Submission status: Accepted

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

n = int(input())
d = [0]*(n+1)
for i in range(2, n+1):
    for j in prime_decomposition(i):
        d[j] += 1
d.sort(reverse=True)
nums = [0]*5
for i in d:
    if i >= 74: j = 5
    elif i >= 24: j = 4
    elif i >= 14: j = 3
    elif i >= 4: j = 2
    elif i >= 2: j = 1
    else: j = 0
    for k in range(j):
        nums[4-k] += 1
print(nums[0]+(nums[1]*(nums[4]-1)+(nums[2]*(nums[3]-1))+nums[3]*(nums[3]-1)*(nums[4]-2)//2))

Submission status: Accepted

Solution code:
n = int(input())

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

li = []

for i in range(1,n+1):
    li += prime_factorize(i)

from collections import Counter

C = Counter(li)

a = 0
b = 0
c = 0
d = 0
e = 0

for i,j in C.items():
    if j >= 74:
        e += 1
    elif 24 <= j < 74:
        d += 1
    elif 14 <= j < 24:
        c += 1
    elif 4 <= j < 14:
        b += 1
    elif 2 <= j < 4:
        a += 1

point = 0

#75
point += e
#25 3
point += (d+e)*(a+b+c)+(d+e-1)*(d+e)
#15 5
point += (c+d+e)*b+(c+d+e-1)*(c+d+e)
#2 5 5
f = b+c+d+e
point += a*f*(f-1)//2+f*(f-1)*(f-2)//2

print(point)

Submission status: Accepted

Solution code:
n=int(input())
e=[0 for i in range(n+1)]
for i in range(2,n+1):
  for j in range(2,i+1):
    if i==1:
      break
    while i%j==0:
      i//=j
      e[j]+=1

def num(k):
  ret=0
  for i in range(n):
    if e[i]>=k-1:
      ret += 1
  return ret
print(num(75) + num(25) * (num(3) - 1) + num(15) * (num(5) - 1) + num(5) * (num(5) - 1) * (num(3) - 2) // 2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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

n=I()
#print(prime_factorize(6))
c=Counter(prime_factorize(n))
st=[74,24,14,4,2]
nums=[]
for y in st:
    count=0
    for x in c.keys():
        if c[x]>=y:
            count+=1
    nums.append(count)
#print(nums)
ans=nums[0]+nums[1]*max(0,(nums[4]-1))+nums[2]*max(0,(nums[3]-1))+nums[3]*max(0,(nums[3]-1))//2*max(0,(nums[4]-2))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
d=np.zeros(101)
def factorization(n):
    temp = n
    for i in range(2, int(n**0.5)+1):
        if temp%i==0:
            while temp%i==0:
                d[i]+=1
                temp //= i
    if temp!=1:
        d[temp]+=1
def cnt(k):
    return len(d[d>=k])
for i in range(2,n+1):
    factorization(i)
print(cnt(74)+cnt(24)*(cnt(2)-1)+cnt(14)*(cnt(4)-1)+cnt(4)*(cnt(4)-1)*(cnt(2)-2)//2)

Submission status: Accepted

Solution code:
from collections import defaultdict
import numpy as np
from itertools import permutations, combinations
n=int(input())
d=defaultdict(int)
def factorization(n):
    temp = n
    for i in range(2, int(n**0.5)+1):
        if temp%i==0:
            while temp%i==0:
                d[i]+=1
                temp //= i

    if temp!=1:
        d[temp]+=1
for i in range(2,n+1):
    factorization(i)
d=np.array(list(d.values()))
ans=0
ans+=len(d[d>=74])
d1=d[d>=2]
d2=d[d>=4]
for x,y in permutations(d1,2):
    if y>=24:
        ans+=1
for x,y in permutations(d2,2):
    if y>=14:
        ans+=1
ans1=0
for x,y,z in permutations(d1,3):
    if y>=4 and z>=4:
        ans1+=1
print(ans+ans1//2)

Submission status: Accepted

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

n = int(input())
if n == 1:
    print(0)
    exit()
dic = {}
for i in range(2,n+1):
    l = prime_factor(i)
    for x in l:
        if x in dic:
            dic[x] += 1
        else:
            dic[x] = 1
a,b,c,d,e = 0,0,0,0,0
for x in dic.values():
    if x >= 74:
        e += 1
    elif x >= 24:
        d += 1
    elif x >= 14:
        c += 1
    elif x >= 4:
        b += 1
    elif x >= 2:
        a += 1
ans = e #75
ans += (d + e) * (a + b + c) + (d + e) * (d + e - 1) #25*3
ans += (d + e + c) * b + (d + e + c) * (d + e + c- 1) #15*5
f = b + c + d + e
ans += f * (f - 1) // 2 * a + f * (f - 1) * (f - 2) // 2  #5*5*3
print(ans)

Submission status: Accepted

Solution code:
A=int(input())
dict_f={}
def divisor(N):
   l={}
   for i in range(2,N+1):
      cnt=0
      while N%i==0:
         cnt+=1
         N//=i
      if cnt>0:
         l[i]=cnt
   return l
for i in range(2,A+1):
   D=divisor(i).items()
   for j,k in D:
      try:
         dict_f[j]=dict_f[j]+k
      except KeyError:
         dict_f[j]=k
dict_f=dict_f.values()
def num(N):
   return len(list(filter(lambda x: x >= N-1, dict_f)))
print(num(75)+num(25)*(num(3)-1)+num(15)*(num(5)-1)+num(5)*(num(5)-1)*(num(3)-2)//2)

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())

N = I()

prime = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

d = {}  # d[p] = Nがpで最大何回割り切れるか
for p in prime:
    r = 0
    for i in range(1,7):
        r += N//(p**i)
    d[p] = r

A = 0  # d[p] >= 74 たるpの個数
B = 0  # d[p] >= 24 たるpの個数
C = 0  # d[p] >= 14 たるpの個数
D = 0  # d[p] >= 4 たるpの個数
E = 0  # d[p] >= 2 たるpの個数

for p in prime:
    if d[p] >= 74:
        A += 1
    if d[p] >= 24:
        B += 1
    if d[p] >= 14:
        C += 1
    if d[p] >= 4:
        D += 1
    if d[p] >= 2:
        E += 1

# 順に、p**74,p**24×q**2,p**14×q**4,p**4×q**4×r**2 の個数を加える

print(A+B*(E-1)+C*(D-1)+((D*(D-1))//2)*(E-2))

Submission status: Accepted

Solution code:
def fac(n):  #nは2以上
    a=[]
    t=n
    if t%2==0:
        count=0
        while t%2==0:
            count+=1
            t//=2
        a.append([2,count])

    for i in range(3,n+1,2):
        if i*i>n:
            break
        if t%i==0:
            count=0
            while t%i==0:
                count+=1
                t//=i
            a.append([i,count])

    if t!=1:
        a.append([t,1])
    
    return a

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())

    d=dict()
    for i in range(1,n+1):
        li=fac(i)
        for p in li:
            if p[0] not in d:
                d[p[0]]=p[1]
            else:
                d[p[0]]+=p[1]

    cnt_75=0
    cnt_25=0
    cnt_15=0
    cnt_5=0
    cnt_3=0
    for v in d.values():
        if v>=74:
            cnt_75+=1; cnt_25+=1; cnt_15+=1; cnt_5+=1; cnt_3+=1
        elif v>=24:
            cnt_25+=1; cnt_15+=1; cnt_5+=1; cnt_3+=1
        elif v>=14:
            cnt_15+=1; cnt_5+=1; cnt_3+=1
        elif v>=4:
            cnt_5+=1; cnt_3+=1
        elif v>=2:
            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)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def f(n):
    return len(list(filter(lambda x: x >= n - 1, l)))
n = int(input())
l = [0] * (n + 1)
for i in range(2, n+1):
    cur = i
    for j in range(2, i+1):
        while cur % j == 0:
            l[j] += 1
            cur //= j
print(f(75) + f(25) * (f(3) - 1) + f(15) * (f(5) - 1) + f(5) * (f(5) - 1) * (f(3) - 2) // 2)

Submission status: Accepted

Solution code:
def is_prime(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1 << 32 else [2, 3, 5, 7, 11, 13, 17] if n < 1 << 48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1:
            continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1


def prime_factor(n):
    if n == 1:
        return {1: 1}

    pf = dict()
    r = list(range(2, n + 1))

    while n != 1:
        x = r[0]
        cnt = 0
        while n % x == 0:
            n = n // x
            cnt += 1
        if cnt > 0:
            pf[x] = cnt
        r = list(filter(lambda y: y % x != 0, r))

    return pf


def main():
    from collections import defaultdict
    n = int(input())
    d = defaultdict(int)
    for i in range(1, n + 1):
        p = prime_factor(i)
        for k, v in p.items():
            d[k] += v
    
    f2_, f4_, f14_, f24_, f74_ = 0, 0, 0, 0, 0
    for i in d.values():
        if i >= 2:
            f2_ += 1
        if i >= 4:
            f4_ += 1
        if i >= 14:
            f14_ += 1
        if i >= 24:
            f24_ += 1
        if i >= 74:
            f74_ += 1

    ans = f74_ + f24_ * (f2_ - 1) + f14_ * (f4_ - 1) + f4_ * (f4_ - 1) * (f2_ - 2) // 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
prime = [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]
num = [0 for i in range(len(prime))]
n = int(input())
vec = [i for i in range(1,n+1)]
for i in vec:
  while i>1:
    for j in range(len(prime)):
      if i%prime[j]==0:
        num[j]+=1
        i//=prime[j]
ans=0
for i in range(len(num)):
  for j in range(i+1,len(num)):
    for k in range(len(num)):
      if i==k or j==k:
        continue
      if num[i]>=4 and num[j]>=4 and num[k]>=2:
        #print(prime[i],prime[j],prime[k])
        ans+=1
for i in range(len(num)):
  for j in range(len(num)):
    if i==j:
      continue
    if num[i]>=24 and num[j]>=2:
      ans+=1
    if num[i]>=14 and num[j]>=4:
      ans+=1    
for i in range(len(num)):
  if num[i]>=74:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
# 約数の数 = 素因数分解して、各素因数の(指数 + 1)をかけ合わせたもの
# 例：12 = 2^2 * 3^1 -> 3 * 2 = 6 (1,2,3,4,6,12)
# これが75になるためには、以下のペアを作れる必要がある。この組み合わせを数える
# 75 : 指数が74
# 3 * 25 : 指数が2 , 24
# 5 * 15 : 指数が4 , 14
# 3 * 5 * 5 : 指数が2,4,4

import sys
readline = sys.stdin.readline

N = int(readline())

def factorization(n):
  res = []
  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
      res.append([i,cnt])
  if temp != 1:
    res.append([temp, 1])
  if res == []:
    res.append([n, 1])
  return res

from collections import defaultdict
dic = defaultdict(int)
for i in range(1, N + 1):
  res = factorization(i)
  for r in res:
    dic[r[0]] += r[1]

ans = 0

vals = dic.values()
# 74以上のものを探す
i74 = 0
for v in vals:
  if v >= 74:
    i74 += 1
ans += i74

i2 = 0
i24 = 0
# 2,24以上のものを探す
for v in vals:
  if v >= 24:
    i24 += 1
  elif v >= 2:
    i2 += 1
ans += (i24 * (i24 - 1))
ans += i24 * i2
  
# 5,15以上のものを探す
i4 = 0
i14 = 0
for v in vals:
  if v >= 14:
    i14 += 1
  elif v >= 4:
    i4 += 1
ans += (i14 * (i14 - 1))
ans += i14 * i4

# 2,4,4を探す
i4 = 0
i2 = 0
for v in vals:
  if v >= 4:
    i4 += 1
  elif v >= 2:
    i2 += 1
if i4 >= 3:
  ans += ((i4 * (i4 - 1)) // 2) * (i4 - 2)
ans += ((i4 * (i4 - 1)) // 2) * i2

print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

N = getN()

def prime_factorize(n):
    divisors = []
    # 27(2 * 2 * 7)の7を出すためにtemp使う
    temp = n
    for i in range(2, int(math.sqrt(n)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                # 素因数を見つけるたびにtempを割っていく
                temp //= i
            divisors.append([i, cnt])
    if temp != 1:
        divisors.append([temp, 1])
    if divisors == [] and n != 1:
        divisors.append([n, 1])

    return divisors

primli = [0] * 101
for i in range(1, N + 1):
    for j in prime_factorize(i):
        primli[j[0]] += j[1]
alta = []
for i in primli:
    if i != 0:
        alta.append(i + 1)

prim3 = 0
prim5 = 0
prim15 = 0
prim25 = 0
prim75 = 0
for i in alta:
    if i >= 75:
        prim75 += 1
    if i >= 25:
        prim25 += 1
    if i >= 15:
        prim15 += 1
    if i >= 5:
        prim5 += 1
    if i >= 3:
        prim3 += 1

ans = 0
if prim3 >= 1 and prim5 >= 2:
    # prim5 C 2
    ans += prim5 * (prim5 - 1) // 2 * (prim3 - 2)
if prim15 >= 1 and prim5 >= 1:
    ans += prim15 * (prim5 - 1)
if prim25 >= 1 and prim3 >= 1:
    ans += prim25 * (prim3 - 1)
if prim75 >= 1:
    ans += prim75
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def factorization(n):
    factors = []

    if n < 2:
        return n

    while n % 2 == 0:
        factors.append(2)
        n //= 2

    for i in range(3, int(n ** 0.5) + 5, 2):
        while n % i == 0:
            factors.append(i)
            n //= i

    if n != 1:
        factors.append(n)

    return factors


def main():
    from collections import Counter

    n = int(input())
    counter = Counter()

    for i in range(2, n + 1):
        factors = factorization(i)
        counter.update(factors)

    x1 = len([c for c in counter.values() if c >= 4])
    y1 = len([c for c in counter.values() if c >= 2])
    x2 = len([c for c in counter.values() if c >= 14])
    y2 = len([c for c in counter.values() if c >= 4])
    x3 = len([c for c in counter.values() if c >= 24])
    y3 = len([c for c in counter.values() if c >= 2])
    x4 = len([c for c in counter.values() if c >= 74])

    ans = 0
    ans += (x1 * (x1 - 1) // 2) * (y1 - 2)
    ans += x2 * (y2 - 1)
    ans += x3 * (y3 - 1)
    ans += x4

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())

N = ni()


def choose(n, k):
    num, den = n, 1
    for i in range(1, k):
        num *= n - i
        den *= i + 1
    return num // den


def solve():
    fs = collections.Counter()
    for n in range(2, N + 1):
        k = 2
        while k * k <= n:
            while n % k == 0:
                n //= k
                fs[k] += 1
            k += 1
        if n > 1:
            fs[n] += 1
    p74, p24, p14, p4, p2 = 0, 0, 0, 0, 0
    for k, v in fs.items():
        if v >= 74:
            p74 += 1
        if v >= 24:
            p24 += 1
        if v >= 14:
            p14 += 1
        if v >= 4:
            p4 += 1
        if v >= 2:
            p2 += 1

    a4_4_2 = p4 * (p4 - 1) // 2 * (p2 - 2)
    a14_4 = p14 * (p4 - 1)
    a24_2 = p24 * (p2 - 1)
    a74 = p74
    return a4_4_2 + a14_4 + a24_2 + a74


print(solve())

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def prime_fact_factorial(n):
    global e
    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([x for x in e if x>=m-1])
def main():
    n=int(input())
    prime_fact_factorial(n)
    print(num(75)+num(25)*(num(3)-1)+num(15)*(num(5)-1)
        +num(5)*(num(5)-1)*(num(3)-2)//2)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
N = 100
primes = []
is_prime = [True]*N
for i in range(2,N):
    if is_prime[i]:
        primes.append(i)
        j = 2
        while i*j < N:
            is_prime[i*j] = False
            j += 1

def get(x):
    cnt = 0
    for e in E:
        if e >= x-1:
            cnt += 1
    return cnt

# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N = int(input())

E = [0]*101
for i in range(2,N+1):
    for p in primes:
        while i%p==0:
            E[p] += 1
            i //= p

ans = 0

# e1^74
ans += get(75)

# e1^24, e2^2
ans += get(25) * (get(3)-1)

# e1^14, e2^4
ans += get(15) * (get(5)-1)

# e1^4, e2^4, e3^2
ans += get(5) * (get(5)-1) * (get(3)-2) // 2

print(ans)

Submission status: Accepted

Solution code:
import math
from collections import Counter

N = int(input())
prime_count = Counter()
def prime(n):
    for i in range(2, math.ceil(math.sqrt(n))+1):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1   

for i in range(1, N+1):
    prime(i)

ans = 0
# 75, 25, 15, 5, 3, 1
over75, over1 = [], []
for k, v in prime_count.items():
    if v >= 74:
        over75 += [k]
    elif v >= 1:
        over1 += [k]
#ans += len(over75) * len(over1)
#ans += len(over75) * (len(over75)-1)
ans += len(over75)

over25, over3 = [], []
for k, v in prime_count.items():
    if v >= 24:
        over25 += [k]
    elif v >= 2:
        over3 += [k]
ans += len(over25) * len(over3)
ans += len(over25) * (len(over25)-1)

over15, over5 = [], []
for k, v in prime_count.items():
    if v >= 14:
        over15 += [k]
    elif v >= 4:
        over5 += [k]
ans += len(over15) * len(over5)
ans += len(over15) * (len(over15)-1)

over5, over3 = [], []
for k, v in prime_count.items():
    if v >= 4:
        over5 += [k]
    elif v >= 2:
        over3 += [k]
ans += (len(over5) * (len(over5)-1))//2 * len(over3)
ans += len(over5) * ((len(over5)-1) * (len(over5)-2)) // 2
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc114/tasks/abc114_d
# https://betrue12.hateblo.jp/entry/2018/12/02/224027
# https://coonevo.hatenablog.com/entry/2020/03/18/192431

from collections import defaultdict

MAX_N = 101

def solve():
    n = int(input())
    # dp[i][j]: i番目までの素因数で約数をj個持つ数の個数
    # 2 ~ n までの素因数分解 (これがn!の素因数分解)
    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

    primes = []
    for i in range(n + 1):
        if e[i] > 0:
            primes.append(i)

    dp = [[0] * MAX_N for _ in range(MAX_N)]
    dp[0][1] = 1
    for i in range(len(primes)):
        for j in range(MAX_N):
            for cnt in range(e[primes[i]] + 1):
                dp[i + 1][min(100, j * (cnt + 1))] += dp[i][j]
    print(dp[len(primes)][75])

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

from collections import defaultdict

def solve():
    n = int(input())
    
    # 32400 = 2^4 3^4 5^2
    # => 5 x 5 x 3 = 75
    # 75の分割分だけ持てば良い

    # 10! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10
    # 10! = 1 x 2 x 3 x (2x2) x 5 x (2x3) x 7 x (2x2x2) x (3x3) x (2x5)
    # 10!の約数 nCk個取ってきた積で割り切れる
    # 1を除いてちょうど74個あるかどうか

    # 2 ~ n までの素因数分解
    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)))

    v1 = num(75) # 75乗を作れるやつ
    v2 = num(25) * (num(3) - 1) # 25乗 x 3乗 (25乗に使った分を含まない)
    v3 = num(15) * (num(5) - 1) # 15乗 x 5乗
    v4 = num(5) * (num(5) - 1) * (num(3) - 2) // 2 # 5乗 x 5乗(-1) x 3乗(-2)
    ans = v1 + v2 + v3 + v4
    # print(e)
    # print(v1)
    # print(v2)
    # print(v3)
    # print(v4)
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())

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

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr

d = {}
for i in range(2,N+1):
    for j in factorization(i):
        if j[0] not in d:
            d[j[0]] = j[1]
        else:
            d[j[0]] += j[1]

ans = 0
#74
for k in d.keys():
    if d[k] >= 74:
        ans += 1
#2 24
c2 = 0
c24 = 0
for k in d.keys():
    if d[k] >= 2:
        c2 += 1
    if d[k] >= 24:
        c24 += 1
ans += c24*(c2-1)
#4 14 
c4 = 0
c14 = 0
for k in d.keys():
    if d[k] >= 4:
        c4 += 1
    if d[k] >= 14:
        c14 += 1
ans += c14*(c4-1)
#2 4 4
ans += c4*(c4-1)*(c2-2)//2

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

f = [-1 for i in range(n//2+5)]

for i in range(2,n//2+5):
    if f[i]==-1:
        f[i]=True
        for j in range(i+i,n//2+5,i):
            f[j] = False

f[0]=False
f[1]=False

lis = []
for i in range(n//2+5):
    if f[i]:
        lis.append(i)

div = []

for i in lis:
    num=n
    s=0
    while num>=1:
        num//=i
        s+=num
    div.append(s)

lis2 = [0 for i in range(5)]
for i in div:
    if i>=74:
        lis2[4]+=1
    if i>=24:
        lis2[3]+=1
    if i>=14:
        lis2[2]+=1
    if i>=4:
        lis2[1]+=1
    if i>=2:
        lis2[0]+=1
ans = 0

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

print(int(ans))

Submission status: Accepted

Solution code:
N = int(input())
fact = {}
for p in range(1,N+1):
    pf={}
    m=p
    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

    for key,value in pf.items():
        if key in fact.keys():
            fact[key] += value
        else:
            fact[key] = value

L = list(fact.values())
n75 = 0
n25 = 0
n15 = 0
n5 = 0
n3 = 0
n1 = 0
for m in L:
    m += 1
    if m>=75:
        n75+=1
    if m>=25:
        n25+=1
    if m>=15:
        n15+=1
    if m>=5:
        n5+=1
    if m>=3:
        n3+=1
    if m>=1:
        n1+=1

cnt = []
cnt.append(n75)
cnt.append(n25*(n3-1))
cnt.append(n15*(n5-1))
cnt.append(( n5*(n5-1)//2 )*(n3-2))
# print(n1,n3,n5,n15,n25,n75)
# print(cnt)
print(sum(cnt))

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict
def input(): return sys.stdin.readline().strip()


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    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())
    if N < 10:
        print(0)
        return
    table = get_sieve_of_eratosthenes(N)
    #print(table)
    primes = defaultdict(int)
    for n in range(2, N + 1):
        for p in table:
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            primes[p] += cnt
    #print(primes)
    
    over_3 = 0
    over_5 = 0
    over_15 = 0
    over_25 = 0
    over_75 = 0
    for p in primes:
        if primes[p] >= 2: over_3 += 1
        if primes[p] >= 4: over_5 += 1
        if primes[p] >= 14: over_15 += 1
        if primes[p] >= 24: over_25 += 1
        if primes[p] >= 74: over_75 += 1
    #print(over_3)
    #print(over_5)
    #print(over_15)
    #print(over_25)
    #print(over_75)
    
    val1 = over_5 * (over_5 - 1) * (over_3 - 2) // 2
    val2 = over_15 * (over_5 - 1)
    val3 = over_25 * (over_3 - 1)
    print(val1 + val2 + val3 + over_75)

    




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


def read():
    N = int(input())
    return N,


def sieve(n):
    """
    n以下の素数を昇順に列挙する
    """
    is_prime = [True for i in range(n+1)]
    primes = []
    for i in range(2, n+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, n+1, i):
                is_prime[j] = False
    return primes


def prime_factorization(n, primes):
    """
    nの素因数分解を求める
    """
    prime_factors = defaultdict(int)
    if n < 2:
        return prime_factors
    for p in primes:
        if p * p > n:
            break
        while n % p == 0:
            prime_factors[p] += 1
            n //= p
    if n > 1:
        prime_factors[n] = 1
    return prime_factors


def divisor(n, primes):
    d = []
    for i in range(1, n+1):
        if i * i > n:
            break
        if n % i == 0:
            d.append(i)
            if i != n // i:
                d.append(n // i)
    return list(sorted(d))


def solve(N):
    primes = sieve(N)
    factors = defaultdict(int)
    for x in range(1, N+1):
        pf = prime_factorization(x, primes)
        for p, v in pf.items():
            factors[p] += v
    V = [v for v in factors.values()]
    
    c = defaultdict(int)
    for v in V:
        for x in [3, 5, 15, 25, 75]:
            if v+1 >= x:
                c[x] += 1
    count = 0
    # (75) 
    count += c[75]
    # (25, 3)
    count += c[25] * (c[3]-1)
    # (15, 5)
    count += c[15] * (c[5]-1)
    # (5, 5, 3)
    count += (c[5] * (c[5]-1) // 2) * (c[3]-2)

    return count

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Accepted

Solution code:
n=int(input())

def prime_fact(x):
    fact=[]
    for i in range(2, int(x**(0.5))+1):
        while x%i==0:
            fact.append(i)
            x//=i
    if x!=1:
        fact.append(x)
    if not fact:
        fact=[x]
    return fact

def eratosthenes(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]]
p=eratosthenes(100)
d={}
for p_i in p:
    d[p_i]=0
for i in range(2,n+1):
    pf=prime_fact(i)
    for pf_i in pf:
        d[pf_i]+=1

cnt74=0
cnt24=0
cnt14=0
cnt4=0
cnt2=0

for key in d:
    if d[key]>=74:
        cnt74+=1
    if d[key]>=24:
        cnt24+=1
    if d[key]>=14:
        cnt14+=1
    if d[key]>=4:
        cnt4+=1
    if d[key]>=2:
        cnt2+=1

print(int(cnt74+(cnt2-1)*cnt24+(cnt4-1)*cnt14+(cnt2-2)*cnt4*(cnt4-1)/2))