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())
if n < 9:
  print(0)
  
else:
  # 素数のリスト作成
  primes = [2]
  for i in range(3, n+1):
    for prime in primes:
      if i % prime == 0:
        break
    else:
      primes.append(i)

  # 素因数の個数のディクショナリ
  fracs = {}
  for prime in primes:
    fracs[prime] = n // prime
  for i in [4, 8, 16, 32, 64]:
    fracs[2] += n // i
  for i in [9, 27, 81]:
    fracs[3] += n // i
  fracs[5] += n // 25
  fracs[7] += n // 49

  ans = 0
  # 個数が2, 4, 14, 24, 74以上の素因数の個数
  n2, n4, n14, n24, n74 = 0, 0, 0, 0, 0

  for i in fracs.keys():
    if fracs[i] >= 2:
      n2 += 1
      if fracs[i] >= 4:
        n4 += 1
        if fracs[i] >= 14:
          n14 += 1
          if fracs[i] >= 24:
            n24 += 1
            if fracs[i] >= 74:
              n74 += 1
            
  ans += n74 + n24 * (n2 - 1) + n14 * (n4 - 1) + n4 * (n4 - 1) * (n2 - 2) // 2

  print(ans)

Submission status: Accepted

Solution code:
p=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
a=[0 for i in range(len(p))]

n= int(input())
for i in range(n):
  m=i+1
  for j in range(len(p)):
    while m%p[j]==0:
      a[j]+=1
      m=m/p[j]

x=0;y=0;z=0;w=0;u=0
for i in range(len(a)):
  if a[i]>=74:
    x+=1
  if a[i]>=24:
    y+=1
  if a[i]>=14:
    z+=1
  if a[i]>=4:
    w+=1
  if a[i]>=2:
    u+=1
print(int(x+y*(u-1)+z*(w-1)+w*(w-1)/2*(u-2)))

Submission status: Accepted

Solution code:
def main():
    N = int(input())

    if N == 1:
        print(0)
    else:
        def prime_list(n):
            prime = [True for _ in range(n+1)]
            prime[0] = False
            prime[1] = False
            for i in range(2,int(n**0.5)+1):
                if not prime[i]:
                    continue
                for j in range(i*2,n+1,i):
                    prime[j] = False
            return [i for i in range(n+1) if prime[i]]

        prime_list = prime_list(N//2)
        cnt_list = [0 for _ in range(len(prime_list))]
        for i in range(len(prime_list)):
            count = 0
            d = N
            while d >= 1:
                count += d//(prime_list[i])
                d //= prime_list[i]
            cnt_list[i] = count

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

if n == 1 or n == 2 or n == 3:
    ans = 0
else:
    prime = [2,3]
    fac = [0] * (n+1)
    fac[2] = 1
    fac[3] = 1
    for i in range(4,n+1):
        ii = i
        for j in range(2,i+1):
            det = 0
            if j in prime:
                if ii % j == 0:
                    det = 1
                while ii % j == 0:
                    fac[j] += 1
                    ii = ii // j
            if det == 0:
                prime.append(ii)
    
    #print(fac)
    c = [0] * 5
    for k in range(2,n+1):
        if fac[k] >= 74:
            c[4] += 1
        if fac[k] >= 24:
            c[3] += 1
        if fac[k] >= 14:
            c[2] += 1
        if fac[k] >= 4:
            c[1] += 1
        if fac[k] >= 2:
            c[0] += 1
    #print(c)
    pos = [0] * 4
    pos[0] = (c[1]*(c[1]-1)*(c[0]-2))//2
    pos[1] = c[4]
    pos[2] = c[2]*(c[1]-1)
    pos[3] = c[3]*(c[0]-1)
    ans = sum(pos)

print(ans)

Submission status: Accepted

Solution code:
def main():
    #import sys
    #input = sys.stdin.readline
    N = int(input())
    
    prime = []
    primecount = []
    
    for i in range(1,N+1):
        count = 0
        for j in range(1,i+1):
            if i%j == 0:
                count += 1
        if count == 2:
            prime.append(i)
    
    for i in range(len(prime)):
        tmp = 0
        tmpN = N
        powP = prime[i]
        while tmpN // powP > 0:
            tmp += tmpN//powP
            powP *= prime[i]
        primecount.append(tmp+1)
    
    n3 = 0
    n5 = 0
    n15 = 0
    n25 = 0
    n75 = 0
    for i in range(len(primecount)):
        k = primecount[i]
        if k >= 75:
            n75 += 1
        if k >= 25:
            n25 += 1
        if k >= 15:
            n15 += 1
        if k >= 5:
            n5 += 1
        if k >= 3:
            n3 += 1
    #print(primecount)
    #print(n3,n5,n15,n25,n75)
    
    ans = n25*(n3 - 1) + n5*(n5 - 1)*(n3 - 2)//2 + n15*(n5 - 1) + n75
    print(ans)
    
main()

Submission status: Accepted

Solution code:
from collections import defaultdict


def factorize2(n):
    """
    nの値を素因数分解し、素因数とその指数をtupleにまとめたリストを返す
    e.g.
    [(2, 2), (5, 1)]
    """
    b = 2
    fct = []
    while b * b <= n:
        cnt = 0
        while n % b == 0:
            cnt += 1
            n //= b
        if cnt > 0:
            fct.append((b, cnt))
        b += 1
    if n > 1:
        fct.append((n, 1))
    return fct


# 75 = 5 * 5 * 3
# p^74 / p^24 * q^2 / p^14 * q^4 / p^4 * q^4 * r^2 の形しか七五数になりえない

N = int(input())
pf = defaultdict(int)
for i in range(1, N + 1):
    for p, n in factorize2(i):
        pf[p] += n

c74, c24, c14, c4, c2 = 0, 0, 0, 0, 0
for p, n in pf.items():
    if n >= 74:
        c74 += 1
    if n >= 24:
        c24 += 1
    if n >= 14:
        c14 += 1
    if n >= 4:
        c4 += 1
    if n >= 2:
        c2 += 1

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

Submission status: Accepted

Solution code:

from math import sqrt, ceil

primes = [2]
for n in range(3, 101):
    if any(n % i == 0 for i in range(2, n)):
        continue
    primes.append(n)

def fact(n):
    p = 1
    for i in range(2, n+1):
        p *= i
    return p

def calc_factors(n):
    factors = {}
    for p in primes:
        while n % p == 0:
            factors[p] = factors.get(p, 0)+1
            n //= p
    return factors

def solve(N):
    n = fact(N)
    factors = calc_factors(n)

    nums = {3:0,5:0,15:0,25:0,75:0}
    for p, c in factors.items():
        if c >= 2:
            nums[3] = nums.get(3,0)+1
        if c >= 4:
            nums[5] = nums.get(5,0)+1
        if c >= 14:
            nums[15] = nums.get(15,0)+1
        if c >= 24:
            nums[25] = nums.get(25,0)+1
        if c >= 74:
            nums[75] = nums.get(75,0)+1
    print(sum([
            nums[5] * (nums[5] - 1) * (nums[3]-2) // 2,
            nums[15] * (nums[5] - 1) ,
            nums[25] * (nums[3] - 1) ,
            nums[75] ]))
N = int(input())
solve(N)

Submission status: Accepted

Solution code:
def p(n):
    l=[]
    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]
    for x in p:
        i=1
        c=0
        if x>n:break
        while x**i<=n:
            c+=(n//(x**i))
            i+=1
        l.append(c)
    return l
l=sorted(p(int(input())),reverse=True)
c=0
ln=len(l)
for i in range(ln):
    if l[i]>=74:c+=1
for i in range(ln):
    for j in range(i+1,ln):
        if l[j]>=24:c+=1
        if l[i]>=24 and l[j]>=2:c+=1
        if l[j]>=14:c+=1
        if l[i]>=14 and l[j]>=4:c+=1
for i in range(ln):
    for j in range(i+1,ln):
        for k in range(j+1,ln):
            if l[k]>=4:c+=2
            if l[i]>=4 and l[j]>=4 and l[k]>=2:c+=1
print(c)

Submission status: Accepted

Solution code:
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:
      cur //= j
      l[j] += 1

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

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())
p_dict = {2:1, 3:1}
for num in range(4,N+1):
  is_prime = True
  for prime, cnt in p_dict.items():
    if num%prime == 0:
      p_dict[prime] = cnt + 1
      idx = 2
      while num%(prime**idx) == 0:
        idx += 1
        p_dict[prime] += 1
      is_prime = False
  if is_prime:
    p_dict[num] = 1

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

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:
# -*- coding: utf-8 -*-                                                                              

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:
import collections
import math
def main():
    N = int(input())

    def isPrime(i):
        for j in range(2, int(math.sqrt(i))+1):
            if i % j == 0:
                return False
        return True

    primes = []
    for i in range(2, N+1):
        if isPrime(i):
            primes.append(i)

    d = collections.defaultdict(int)
    for i in range(2, N+1):
        for p in primes:
            while i > 0 and i % p == 0:
                d[p] += 1
                i = i // p
            if i <= 1: break
    p74 = []
    p24 = []
    p14 = []
    p4 = []
    p2 = []

    # 75= 3*5*5, [74], [24, 2], [14, 4], [4, 4, 2]
    for p in d:
        if d[p] >= 74: p74.append(p)
        if d[p] >= 24: p24.append(p)
        if d[p] >= 14: p14.append(p)
        if d[p] >= 4: p4.append(p)
        if d[p] >= 2: p2.append(p)

    # print(p4)
    # print(p2)
    count = 0
    count += len(p74)
    for p in p24:
        if p in p2: count += len(p2)-1
        else: count += len(p2)
    for p in p14:
        if p in p4: count += len(p4)-1
        else: count += len(p4)
    for p in p2:
        # print(count, p)
        if p in p4: count += (len(p4)-1)*(len(p4)-2) // 2
        else: count += (len(p4))*(len(p4)-1) // 2
        # print(count)
    return count

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
n = int(input())
prime_list = [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]
divider_list = []
for i in range(1,n+1):
    while i > 1:
        for j in prime_list:
            if i % j == 0:
                divider_list.append(j)
                i = i // j
                break
            else:
                continue
divider_dic = {}
for k in divider_list:
    if k in divider_dic:
        divider_dic[k] = divider_dic[k] + 1
    else:
        divider_dic[k] = 1

key_list = []
for k in divider_dic:
    key_list.append(divider_dic[k])
a, b, c, d, e = 0, 0, 0, 0, 0
for k in key_list:
    if k == 1:
        continue
    elif k < 4:
        a += 1
    elif k < 14:
        b += 1
    elif k < 24:
        c += 1
    elif k < 74:
        d += 1
    else:
        e += 1

def nCr(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i in range(r)]
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1: 
            result *= numerator[k]
    return result

ans = int(a*nCr(b+c+d+e,2)+nCr(b+c+d+e,2)*(b+c+d+e-2)+b*(c+d+e)+(c+d+e)*(c+d+e-1)+(a+b+c)*(d+e)+(d+e)*(d+e-1)+e)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
pr = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
arr = [0] * 5
num = 1
for i in range(1, n+1):
    num *= i
for n in pr:
    tmp = num
    ct = 0
    while True:
        if tmp % n == 0:
            ct += 1
            tmp //= n
        else:
            break
    if ct >= 74:
        arr[0] += 1
    elif ct >= 24:
        arr[1] += 1
    elif ct >= 14:
        arr[2] += 1
    elif ct >= 4:
        arr[3] += 1
    elif ct >= 2:
        arr[4] += 1
ans = 0
if arr[0] == 1:
    ans += 1
if sum(arr[:2]) >= 1:
    ans += ((sum(arr[0:2]) * (sum(arr) - 1)))
if sum(arr[:3]) >= 1:
    ans += ((sum(arr[0:3]) * (sum(arr[:4]) - 1)))
if sum(arr[:4]) >= 2 and arr[4] >= 1:
    s = sum(arr[:4])
    ans += (s * (s-1) * (s-2) // 2)
    ans += (arr[4] * s * (s-1) // 2)
print(ans)

Submission status: Accepted

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

N = int(input())
memo = {}
for n in range(2, N + 1):
    for k, v in factor(n):
        memo[k] = memo.get(k, 0) + v

def num(n):
    return sum(1 for v in memo.values() if v >= n - 1)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def get_primes_tuple(n):  # including n
    isPrime = [True for _ in range(n+1)]
    isPrime[0] = False
    isPrime[1] = False
    for j in range(4, n+1, 2): isPrime[j] = False  # multiples of 2
    primes = [2]

    for i in range(3, int(n**0.5)+1):
        if not isPrime[i]: continue
        primes.append(i)
        for j in range(i*i, n+1, i+i):  # j = (i*i, (i+2)*i, ..., m*i <= n)
            isPrime[j] = False
    # return tuple(isPrime)
    return tuple(primes)


primes = get_primes_tuple(10000)
def prime_factorization(n):
    pf = []
    for p in primes:
        while n != 1 and n%p == 0:
            pf.append(p)
            n //= p
    return pf


import collections

def main(): 
    n = II()

    pf_of_n_factorial = collections.defaultdict(int)
    for i in range(2, n+1):
        for p in prime_factorization(i):
            pf_of_n_factorial[p] += 1

    import itertools

    ans = 0

    # 1つの素数が75-1個以上ある。
    for i in primes:
        if pf_of_n_factorial[i] >= 74:
            ans += 1

    # 3-1, 25-1 または 5-1, 15-1
    for i, j in itertools.permutations(primes, 2):
        if pf_of_n_factorial[i] >= 2 and pf_of_n_factorial[j] >= 24:
            ans += 1
        if pf_of_n_factorial[i] >= 4 and pf_of_n_factorial[j] >= 14:
            ans += 1

    # 3-1, 5-1, 5-1
    for i, j, k in itertools.permutations(primes, 3):
        if pf_of_n_factorial[i] >= 2 and pf_of_n_factorial[j] >= 4 and pf_of_n_factorial[k] >= 4 and j<k:
            ans += 1

    print(ans)


main()

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
import math, copy


n = int(input())
prime = []
data = [i for i in range(2, n + 10)]
temp = 0
while (temp <= n):
    temp = data[0]
    prime.append(temp)
    data = [e for e in data if e % temp != 0]
n_dict = defaultdict(lambda: 1)
k = math.factorial(n)
for p in prime:
    while (k % p == 0):
        k = k // p
        n_dict[p] += 1
alc = list(n_dict.values())
ans = 0
n_75 = len([a for a in alc if a >= 75])
n_25 = len([a for a in alc if a >= 25])
n_15 = len([a for a in alc if a >= 15])
n_5 = len([a for a in alc if a >= 5])
n_3 = len([a for a in alc if a >= 3])
ans += n_75
if n_25 > 0:
    ans += (n_25 * (n_3 - 1))
if n_15 > 0:
    ans += ((n_5 - 1) * (n_15))
ans += (n_5 * (n_5 - 1) * (n_3 - 2)) // 2
print(ans)

Submission status: Accepted

Solution code:
import math

def nCr(n,r):

    if n >= r:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

    else:
        return 0



N = int(input())

slis = [2]

for i in range(N+1):

    if i <= 2:
        continue;

    flag = True

    for j in slis:

        if i % j == 0:

            flag = False

    if flag:
        slis.append(i)


num = [0] * len(slis)

up1 = 0
up2 = 0
up4 = 0
up14 = 0
up24 = 0
up74 = 0


for i in range(N):

    i += 1

    cnt = 0

    while True:

        if i == 1:
            break

        if i % slis[cnt] == 0:

            i = i // slis[cnt]
            num[cnt] += 1

            if num[cnt] == 74:
                up74 += 1
            elif num[cnt] == 24:
                up24 += 1
            elif num[cnt] == 14:
                up14 += 1
            elif num[cnt] == 4:
                up4 += 1
            elif num[cnt] == 2:
                up2 += 1
            elif num[cnt] == 1:
                up1 += 1
                
        else:
            cnt += 1

#print (slis)
#print (num)

ans = 0


ans += nCr(up74,1)

ans += nCr(up24,1) * nCr(up2-1,1)

ans += nCr(up14,1) * nCr(up4-1,1)

ans += nCr(up4,2) * nCr(up2-2,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)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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

def divisor_list(N): #素因数分解
    res = []
    i = 1
    while i*i < N:
        if N%i == 0:
            res.append(i)
            res.append(N//i)
        i += 1
    if i*i == N: res.append(i)
    return sorted(res)    

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

#n,a = [int(i) for i in readline().split()]
#n,x = [int(i) for i in readline().split()]
n = int(input())

from collections import defaultdict
d = defaultdict(int)

for i in range(1,n+1):
    l = prime_factorize(i)
    for p,e in l:
        d[p] += e


l = sorted([i for i in d.values() if i > 1])

div = divisor_list(75)
#dp[i][j] = 「i 番目の素因数まで見て、約数の個数が j であるような選び方
dp = [[0]*76 for i in range(1+len(l))]
dp[0][1] = 1
for i,c in enumerate(l):
    for j in div:
        for a in div:
            if a <= c+1 and j*a <= 75:
                dp[i+1][j*a] += dp[i][j]

#print(*dp,sep="\n")
print(dp[-1][75])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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
    
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

#n,a = [int(i) for i in readline().split()]
#n,x = [int(i) for i in readline().split()]
n = int(input())

from collections import defaultdict
d = defaultdict(int)

for i in range(1,n+1):
    l = prime_factorize(i)
    for p,e in l:
        d[p] += e


l = sorted([i for i in d.values() if i > 1])

#print(l)
ans = 0

def f(x): return len([i for i in l if i >= x-1])

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

# import math
# def isPrime(x):
#   if x == 2:
#     return True
#   if x % 2 == 0:
#     return False
#   for i in range(3, int(math.sqrt(x)) + 1, 2):
#     if x % i == 0:
#       return False
#   return True

# primes=[]
# for i in range(2,100):
#   if isPrime(i):
#     primes.append(i)


primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
          41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

pows = {}
for p in primes:
  if p > n:
    break
  pows[p] = 0
  pp = p
  while n // pp >= 1:
    pows[p] += n // pp
    pp *= p

e = []
for x in pows.values():
  e.append(x + 1)
# print(e)

import itertools
ans = 0

for x in e:
  if x >= 75:
    ans += 1

for (x, y) in itertools.combinations(e, 2):
  #print(x, y)
  for a, b in [(25, 3), (15, 5), (5, 15), (3, 25)]:
    if x >= a and y >= b:
      ans += 1

for (x, y, z) in itertools.combinations(e, 3):
  #print(x, y, z)
  for a, b, c in [[5, 5, 3], [5, 3, 5], [3, 5, 5]]:
    if x >= a and y >= b and z >= c:
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
# ABC 114 D

def resolve():
    N = int(input())
    e = [0] * (N+1)  # N! を素因数分解した結果の各素数の個数

    for i in range(2, N+1):
        # i の素因数分解を行う
        cur = i
        for j in range(2, i+1):
            while cur % j == 0:
                e[j] += 1
                cur //= j

    # dp[i][j] : i 番目の素因数まで考えたときに約数を j 個もつ数の個数
    dp = [[0] * 76 for _ in range(N+2)]
    dp[0][1] = 1

    for i in range(N+1):
        for have in range(76):
            for take in range(1, e[i]+2):
                if have * take > 75:
                    continue
                dp[i+1][have*take] += dp[i][have]

    print(dp[N][75])


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict
import math
def Prime(n):
    num = int(math.sqrt(n))
    ls = []
    for i in range(2,num+1):
        while 1:
            if n%i == 0:
                n = n//i
                ls.append(i)
            else:
                break
    if n!=1:
        ls.append(n)
    return ls

def main():
    n = int(input())
    dc = defaultdict(int)
    for i in range(2,n+1):
        ls = Prime(i)
        for j in ls:
            dc[j] += 1
    ls = list(dc.values())

    lenth = len(ls)
    ans = 0
    #case1 a^74
    for i in range(lenth):
        if ls[i]>=74:
            ans +=1
    
    #case2 a^24 b^2
    for i in range(lenth):
        for j in range(lenth):
            if i==j:
                continue
            if ls[i]>=24 and ls[j]>=2:
                ans +=1
    
    #case3 a^14 b^4
    for i in range(lenth):
        for j in range(lenth):
            if i==j:
                continue
            if ls[i]>=14 and ls[j]>=4:
                ans +=1
    
    #case4 a^4 b^4 c^2
    for i in range(lenth):
        for j in range(lenth):
            if i==j:
                continue
            for k in range(lenth):
                if i==k or j==k:
                    continue
                if ls[i]>=4 and ls[j]>=4 and ls[k]>=2:
                    
                    ans += 0.5
    print(int(ans))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(int)

N = int(input())


for i in range(2, N+1):
    for j in range(2, i+1):
        while i % j == 0:
            d[j] += 1
            i = i//j
        if i == 1:
            break
# print(d)

c74, c24, c14, c4, c2 = 0, 0, 0, 0, 0
for v in d.values():
    if v >= 74:
        c74 += 1
    if v >= 24:
        c24 += 1
    if v >= 14:
        c14 += 1
    if v >= 4:
        c4 += 1
    if v >= 2:
        c2 += 1


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

Submission status: Accepted

Solution code:
N = int(input())
p = [1] * (N+1)
for i in range(2,N+1):
    j = 2
    while i >= j:
        if i%j == 0:
            p[j] += 1
            i //= j
        else:
            j += 1
    if i > 1:
        p[i] += 1
p.sort(reverse = True)

def num(x):
    i = 0
    while p[i] >= x:
        i += 1
    return i
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())
arr = [0]*(n+1)

for i in range(2, n+1):
  tmp = i
  div = 2
  while(div <= i):
    if(tmp%div == 0):
      arr[div] += 1
      tmp //= div
    else:
      div += 1
    
def count(n):
  return len([i for i in arr if i >= n])

ans = count(74) + count(24)*(count(2)-1) + count(14)*(count(4)-1) + count(4)*(count(4)-1)*(count(2)-2)//2
print(ans)