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:
print([0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 8, 8, 11, 11, 11, 11, 14, 14, 32, 32, 35, 35, 35, 35, 42, 42, 42, 42, 49, 49, 49, 49, 49, 49, 75, 75, 86, 86, 86, 86, 86, 86, 123, 123, 131, 131, 131, 131, 148, 148, 153, 153, 170, 170, 170, 170, 170, 170, 227, 227, 227, 227, 227, 227, 250, 250, 323, 323, 324, 324, 324, 324, 354, 354, 354, 354, 384, 384, 384, 384, 384, 391, 491, 491, 529, 529, 529, 529, 529, 529, 543][int(input())-1])

Submission status: Accepted

Solution code:
n = int(raw_input())

def prime_div(n):
    arr = []
    f = 1
    while f:
        state = 0
        for i in range(2,int(n**2)+1):
            if n % i == 0:
                arr.append(i)
                n /= i
                state = 1
                break
        if state == 0:
            f = 0
    return arr
arr = []
for i in range(n):
    arr += prime_div(i+1)
arr.sort()
num_set = set(arr)
# print num_set
counter = []
counter_num = [0,0,0,0,0]
num_lst = [2, 4, 14, 24, 74]
for num in num_set:
    count = arr.count(num)
    counter.append(count)
    for i in range(5):
        if count >= num_lst[i]:
            counter_num[i]+=1

# print counter_num
ans = 0
# 74
ans += counter_num[4]
# 24 2
if counter_num[3] > 0:
    ans += counter_num[3]*(counter_num[0]-counter_num[3])+counter_num[3]*(counter_num[3]-1)
# 14 4
if counter_num[2] > 0:
    ans += counter_num[2]*(counter_num[1]-counter_num[2])+counter_num[2]*(counter_num[2]-1)
if counter_num[1] > 1:
    ans += counter_num[1]*(counter_num[1]-1)/2*(counter_num[0]-counter_num[1])
if counter_num[1] > 2:
    ans += counter_num[1]*(counter_num[1]-1)/2*(counter_num[1]-2)
print ans

Submission status: Accepted

Solution code:
n = int(input())
d = {}
for i in range(2, n+1):
    for j in range(2, i+1):
        while i%j == 0:
            i //= j
            d[j] = d.get(j, 0)+1
a = list(d.values())
dp = [[0]*74 + [1] for i in range(len(a)+1)]
for i in reversed(range(len(a))):
    for j in range(74):
        for k in range(a[i]+1):
            v = j+(j+1)*k
            if v > 74:
                break
            dp[i][j] += dp[i+1][v]
print(dp[0][0])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Dec  2 21:50:38 2018
ABC114D
@author: maezawa
"""

nmax = int(100)
is_prime = [True]*(nmax+1)

is_prime[0] = False
is_prime[1] = False

for i in range(2, nmax//2):
    if is_prime[i] == True:
        for j in range(2*i,nmax+1,i):
            is_prime[j] = False

prime_numbers = [i for i in range(nmax+1) if is_prime[i]]

n = int(input())

prime_exps = [0]*len(prime_numbers)
for i in range(2,n+1):
    for k, p in enumerate(prime_numbers):
        if i<p:
            break
        while i>=p:
            if i%p == 0:
                i = i // p
                prime_exps[k] += 1
            else:
                break

#print(prime_numbers)
#print(prime_exps)
ans = 0

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

# searching >=74
for i in prime_exps:
    if i>=74:
        cnt74 += 1
    if i>=24:
        cnt24 += 1
    if i>=14:
        cnt14 += 1
    if i>=4:
        cnt4 += 1
    if i>=2:
        cnt2 += 1

cnt = cnt74
if cnt24 > 0 and cnt2 > 1:
    cnt += cnt24*(cnt2-1)
if cnt14 > 0 and cnt4 > 1:
    cnt += cnt14*(cnt4-1)
if cnt4 > 1 and cnt2 > 2:
    cnt += cnt4*(cnt4-1)//2*(cnt2-2)
    
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
e = [0 for _ in range(N + 1)]

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


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


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

print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy


def mk_array(init_val, *args):
    args = args[::-1]
    res = [init_val for _ in range(args[0])]
    for arg in args[1:]:
        res = [deepcopy(res) for _ in range(arg)]
    return res


N = int(input())
e = [0 for _ in range(N + 1)]

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

counts = list(filter(lambda x: x > 0, e))
prim_count = len(counts)
counts = [0] + counts  # 1-indexed 化
dp = mk_array(0, prim_count + 1, 75 + 1)
dp[0][1] = 1

for i in range(1, prim_count + 1):
    for j in range(1, 75 + 1):
        for k in range(min(counts[i], 75 // j - 1) + 1):
            dp[i][j * (k + 1)] += dp[i - 1][j]

print(dp[prim_count][75])

Submission status: Accepted

Solution code:
import math
n = int(input())

insu = {}
for i in range(2, n + 1):
    count = 0
    for j in insu:
        while i % j == 0:
            count += 1
            if j in insu:
                insu[j] += 1
            else:
                insu[j] = 1
            i //= j
    if count == 0:
        insu[i] = 1

insu = sorted(insu.items(), key=lambda x: -x[1])

count = 0
debug = []
def dfs(now, conb, mst):
    global count, insu
    if len(conb) == len(mst):
        count += 1
        debug.append(conb)
    else:
        for i in range(now, len(insu)):
            if insu[i][1] >= mst[len(conb)]:
                dfs(i + 1, conb + [insu[i][0]], mst)
dfs(0, [], [74])
dfs(0, [], [24, 2])
dfs(0, [], [2, 24])
dfs(0, [], [14, 4])
dfs(0, [], [4, 14])
dfs(0, [], [2, 4, 4])
dfs(0, [], [4, 2, 4])
dfs(0, [], [4, 4, 2])
print(count)

Submission status: Accepted

Solution code:
N = int(input())
p = [0] * (N+1)


def is_prime(n):
    for i in range(2, n):
        if not n % i:
            return False
    return True


def n(m):
    return sum([True for i in p if i >= m])


l = [i for i in range(2, N+1) if is_prime(i)]
for i in range(2, N+1):
    for j in l:
        while not i % j:
            p[j] += 1
            i //= j

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

Submission status: Accepted

Solution code:
N = int(input())

prime = [2]

for i in range(2, 101):
    for j in range(2, i-1):
        if i % j == 0:
            break
    else:
        prime.append(i)

factor = [0] * 101

for i in range(1, N+1):
    for p in prime:
        if i == 1:
            break
        while i % p == 0:
            i /= p
            factor[p] += 1

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

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 math import sqrt
from bisect import bisect_left as bi
n = int(input())
x,z = [0]*98,[]
for i in range(2,n+1):
	m = i
	while 1:
		f = 0
		for j in range(2,int(sqrt(m))+1):
			if m%j==0:
				x[j]+=1
				f = 1
				break
		if f: m//=j
		else:
			x[m]+=1
			break
for i in x[::-1]:
	if i>1: z.append(i)
p = len(z)
print(p-bi(z,74)+max((p-bi(z,24))*(p-bi(z,2)-1),0)+max((p-bi(z,14))*(p-bi(z,4)-1),0)+max((p-bi(z,4))*(p-bi(z,4)-1)*(p-bi(z,2)-2)//2,0))

Submission status: Accepted

Solution code:
n=int(input())
f=[]
w=[0,0,0,0,0]
for i in range(2,n+1):
    c=0
    r=int(i**0.5)
    for j in range(2,r+2):
        while i%j==0:
            c+=1
            i=i//j
        if c!=0:
            f.append([j,c])
            c=0
    if i!=1:
        f.append([i,1])
f.sort()
d=[]
ans=0
if n!=1:
    cou=f[0][1]
    for i in range(1,len(f)):
        if f[i][0]==f[i-1][0]:
            cou+=f[i][1]
        else:
            d.append(cou)
            cou=1
    d.append(cou)

    for i in d:
        for j,num in enumerate([2,4,14,24,74]):
            if i>=num:
                w[j]+=1
    ans=w[4]+w[3]*(w[0]-1)+w[2]*(w[1]-1)+w[1]*(w[1]-1)*(w[0]-2)//2
print(ans)

Submission status: Accepted

Solution code:
ps=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
n=int(input())
factor=[0]*len(ps)
for i in range(2,n+1):
    for j in range(len(ps)):
        p=ps[j]
        while True: 
            if i%p==0:
                i//=p
                factor[j]+=1
            else:
                break
res=0
if factor[0]>=74:
    res+=1
for i in range(len(ps)):
    for j in range(i+1,len(ps)):
        if factor[i]>=2 and factor[j]>=24:
            res+=1
        if factor[i]>=4 and factor[j]>=14:
            res+=1
        if factor[i]>=14 and factor[j]>=4:
            res+=1
        if factor[i]>=24 and factor[j]>=2:
            res+=1
for i in range(len(ps)):
    for j in range(i+1,len(ps)):
        for k in range(j+1,len(ps)):
            if factor[i]>=2 and factor[j]>=4 and factor[k]>=4:
                res+=1
            if factor[i]>=4 and factor[j]>=2 and factor[k]>=4:
                res+=1
            if factor[i]>=4 and factor[j]>=4 and factor[k]>=2:
                res+=1
print(res)

Submission status: Accepted

Solution code:
import math 
  
# A function to print all prime factors of  
# a given number n 
def primeFactors(n): 
      
    # Print the number of two's that divide n 
    while n % 2 == 0: 
        arr[2] = arr[2] + 1 
        n = int(n / 2)
          
    # n must be odd at this point 
    # so a skip of 2 ( i = i + 2) can be used 
    for i in range(3,int(math.sqrt(n))+1,2): 
          
        # while i divides n , print i ad divide n 
        while n % i== 0: 
            arr[i] = arr[i] + 1  
            n = int(n / i)
              
    # Condition if n is a prime 
    # number greater than 2 
    if n > 2: 
        arr[n] = arr[n] + 1  

# for n in range(0,101):
arr = [0] * 101
wow = [0] * 5
result = 0
n = int(input())

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

# count = 0
for i in arr:
    # if i != 0:
    #     print(count, i)
    # count = count + 1
    if i > 1: wow[0] = wow[0] + 1
    if i > 3: wow[1] = wow[1] + 1
    if i > 13: wow[2] = wow[2] + 1
    if i > 23: wow[3] = wow[3] + 1
    if i > 73: wow[4] = wow[4] + 1

# for i in wow:
#     if i != 0:
#         print(i)

x = wow[4]
y = wow[3] * (wow[0] - 1)
z = wow[2] * (wow[1] - 1)
a = wow[1] * (wow[1] - 1) * (wow[0] - 2) // 2
result = wow[4] + wow[3] * (wow[0] - 1) + wow[2] * (wow[1] - 1) + wow[1] * (wow[1] - 1) * (wow[0] - 2) // 2
print(result)

Submission status: Accepted

Solution code:
def make_divisor_list(num): # 約数を求める
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        i = 1
        while i*i <= num:
            if num%i == 0:
                divisor_list.append(i)
                divisor_list.append(num//i)

            i += 1
        divisor_list.append(num)

        return sorted(set(divisor_list))

def factorial(n): # 階乗を求める
    if n == 0 or n == 1:
        return 1
    else:
        ans = n*factorial(n-1)

        return ans
def usage(n):

    fct = factorize(n)
    return fct

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

def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

N = int(input())

NN = factorial(N)
usa = usage(NN)

ans = 0
div_75 = [3, 5, 15, 25, 75]


nums = [0 for _ in range(75+1)]

for i in usa:
    for divs in div_75:
        if i[1] >= divs-1:
            nums[divs] = nums[divs] + 1

ans = 0

if nums[5] >= 2:
    num_tmp = nums[5]
    tmp = factorial(num_tmp)//(2*factorial(num_tmp-2))
    ans += (nums[3] - 2) * tmp

if nums[15] >= 1:
    num_tmp = nums[15]
    tmp = num_tmp
    ans += (nums[5] - 1) * tmp

if nums[25] >= 1:
    tmp = nums[25]
    ans += (nums[3] - 1) * tmp

if nums[75] >= 1:
    ans += nums[75]


print(ans)

Submission status: Accepted

Solution code:
from collections import Counter as c
from itertools import permutations as p

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

n=int(input())
d=c()
for i in range(1,n+1):
    d+=fact(i)

f=lambda n,x:sum(1 for i in p(d.values(),n) if all(map(lambda x,y:x>=y,i,x)))
print(f(3,(2,4,4))//2+f(2,(2,24))+f(2,(4,14))+f(1,(74,)))

Submission status: Accepted

Solution code:
from collections import Counter as c
from itertools import permutations as p

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

n=int(input())
d=c()
for i in range(1,n+1):
    d+=fact(i)

v=sum(1 for i,j,k in p(d.values(),3) if i>=2 and j>=4 and k>=4)//2
v+=sum(1 for i,j in p(d.values(),2) if i>=2 and j>=24)
v+=sum(1 for i,j in p(d.values(),2) if i>=4 and j>=14)
v+=sum(1 for i in d.values() if i>=74)

print(v)

Submission status: Accepted

Solution code:
N = int(input())
primes = {}
for p in map(int, '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'.split()):
    primes[p] = 0
factors = {}
for p in primes.keys():
    factors[p] = 0
for i in range(1, N + 1):
    while i > 1:
        for p in primes:
            while i % p == 0:
                factors[p] = factors.get(p, 0)+1
                i //= p
fact3, fact5, fact15, fact25, fact75 = 0, 0, 0, 0, 0
for k, v in factors.items():
    if v >= 74:
        fact75 += 1
    if v >= 24:
        fact25 += 1
    if v >= 14:
        fact15 += 1
    if v >= 4:
        fact5 += 1
    if v >= 2:
        fact3 += 1
print(fact75 + fact25 * (fact3 - 1) + fact15 *
      (fact5 - 1) + fact5 * (fact5 - 1) * (fact3 - 2) // 2)

Submission status: Accepted

Solution code:
from collections import defaultdict


def is_prime(n: int)-> bool:
    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False
    # when n is a prime number
    # x^(n-1) ≡ 1 (mod n)
    return pow(2, (n-1), n) == 1


def prime_factorize(n: int):
    prime_factors = []
    range_max = int(n //2) + 1

    for i in range(2, range_max):
        if not is_prime(i):
            continue
        while True:
            div, mod = divmod(n, i)
            if mod == 0:
                prime_factors.append(i)
                n = div
            else:
                break
        if n == 1:
            break
    prime_factors.append(n)
    return prime_factors


prime_factors_dict = {0: {}}

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

    for i in range(1,n+1):
        prime_factors = prime_factorize(i)
        this_prime_factors = defaultdict(int)
        for pm in prime_factors:
            this_prime_factors[pm] += 1

        for k, v in prime_factors_dict[i-1].items():
            this_prime_factors[k] += v
        prime_factors_dict[i] = this_prime_factors

    this_prime_factors = prime_factors_dict[n]

    prime_factors_list = sorted(list(filter(lambda x:x[0] != 1, this_prime_factors.items())))

    cnt_mt_74times = len(list(filter(lambda x: x[1] >= 74, prime_factors_list)))
    cnt_mt_24times = len(list(filter(lambda x: x[1] >= 24, prime_factors_list)))
    cnt_mt_14times = len(list(filter(lambda x: x[1] >= 14, prime_factors_list)))
    cnt_mt_4times  = len(list(filter(lambda x: x[1] >= 4, prime_factors_list)))
    cnt_mt_2times  = len(list(filter(lambda x: x[1] >= 2, prime_factors_list)))

    ans_cnt = 0

    # q^74
    ans_cnt += cnt_mt_74times

    # q^24 * p^2
    ans_cnt += cnt_mt_24times * (cnt_mt_2times - 1)

    # q^14 * p^4
    ans_cnt += cnt_mt_14times * (cnt_mt_4times - 1)

    # q^4 * p^4 * r^2
    ans_cnt += cnt_mt_4times * (cnt_mt_4times - 1) // 2 * (cnt_mt_2times - 2)

    print(ans_cnt)

    return



main()

Submission status: Accepted

Solution code:
# 因数を昇順に全列挙
from collections import Counter
import math
def com(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
fac_list = []
def factoring(n):
    for i in range(2,n+1):
        if n % i == 0:
            fac_list.append(i)
            n = n // i
            break
    if n == 1:
        return fac_list
    else:
        return factoring(n)
# (素因数,指数)
n = int(input())
c = list(Counter(factoring(math.factorial(n))).values())
# 指数 (2,4,4),(2,24),(4,14),(74) の場合の数
l = [0]*5 # [2,4,14,24,74]
for e in c:
    if e >= 74:
        index = 4
    elif e >= 24:
        index = 3
    elif e >= 14:
        index = 2
    elif e >= 4:
        index = 1
    elif e >= 2:
        index = 0
    else:
        continue
    l[index] += 1
sum_l = sum(l)
num_74 = l[4]
if sum_l - l[0] - 1 > 0:
    num_4_14 = (l[2] + l[3] + l[4])*(sum_l - l[0] - 1)
else:
    num_4_14 = 0
if sum_l - 1 > 0:
    num_2_24 = (l[3] + l[4])*(sum_l - 1)
else:
    num_2_24 = 0
if sum_l - l[0] >= 2:
    num_2_4_4 = com(sum_l-l[0],2)*(sum_l - 2)
else:
    num_2_4_4 = 0
ans = num_74 + num_4_14 + num_2_24 + num_2_4_4
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
fact = []
def init():
  fact.append(0)
  for i in range(1,101):
    fact.append(0)

def solve(n):
  cnt = 0
  for i in range(1,n+1):
    tp = i
    di = 2
    while tp != 1:
      if tp % di == 0:
        fact[di] += 1
        cnt += 1
        tp /= di
      else:
        di += 1
  sf = []
  tf = [] 
  ft = []
  f = []
  t = []
  for i in range(1,101):
    if fact[i] >= 74:
      sf.append(i)
    if fact[i] >= 24:
      tf.append(i)
    if fact[i] >= 14:
      ft.append(i)
    if fact[i] >= 4:
      f.append(i)
    if fact[i] >= 2:
      t.append(i)
  ans = len(sf)
  for i in tf:
    for j in t:
      if i != j:
        ans += 1
  for i in ft:
    for j in f:
      if i != j:
        ans += 1
  for i in f:
    for j in f:
      if i < j:
        for k in t:
          if i != k and j != k:
            ans += 1  
  return ans

n = int(input())
init()
print(solve(n))

Submission status: Accepted

Solution code:
import copy
def getPrimes(n):
    res = {}
    for i in range(2, n+1):
        if n % i == 0:
            res[i] = 0
            while n % i == 0:
                res[i] = res[i] + 1
                n = n // i
        if i * i > n:
            break;
        
    if n != 1:
        res[n] = 1
    return res

def add(a, b):
    res = copy.deepcopy(a)
    for i in b:
        if i in res:
            res[i] = res[i] + b[i]
        else:
            res[i] = b[i]
    return res

N = int(input())
cnt = {}
for i in range(1, N+1):
    cnt = add(cnt, getPrimes(i))

num = []
for i in cnt:
    num.append(cnt[i])
num.sort()
ans  = 0
for i in range(len(num)):
    for j in range(len(num)):
        for k in range(j + 1, len(num)):
            if i == j or i == k:
                continue
            if num[i] >= 2 and num[j] >= 4 and num[k] >= 4:
                ans = ans + 1
                
for i in range(len(num)):
    for j in range(len(num)):
        if i != j and num[i] >= 2 and num[j] >= 24:
            ans = ans + 1
            
for i in range(len(num)):
    for j in range(len(num)):
        if i != j and num[i] >= 4 and num[j] >= 14:
            ans = ans + 1
            
for i in range(len(num)):
    if num[i] >= 74:

        
        ans = ans + 1
print(ans)

Submission status: Accepted

Solution code:
def prime(n):
    for i in range(2,n):
        if n%i == 0:
            return False
    return True

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

    f = 1
    for i in range(1,n+1):
        f *= i

    p = []
    for i in range(2,n):
        if prime(i):
            p.append(i)
    P = len(p)

    ans = set()
    for i in range(P):
        x = p[i]**74
        if f%x == 0:
            ans.add(x)

        for j in range(P):
            if i == j:
                continue

            x = p[i]**24 * p[j]**2
            if f%x == 0:
                ans.add(x)

            x = p[i]**14 * p[j]**4
            if f%x == 0:
                ans.add(x)

            for k in range(P):
                if i == k or j == k:
                    continue

                x = p[i]**4 * p[j]**4 * p[k]**2
                if f%x == 0:
                    ans.add(x)

    print(len(ans))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import factorial as f

N = int(input())

primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
divs = []
for i in range(1,101):
    tmp = [0 for _ in range(len(primes))]
    for j in range(len(primes)):
        p = primes[j]
        tmp[j] = 0
        while(i//p==i/p):
            i = i//p
            tmp[j] += 1
    divs.append(tmp)
#print(divs)

divsum = [0 for _ in range(len(primes))]
for i in range(1, N+1):
    for j in range(len(primes)):
        divsum[j] += divs[i-1][j]
#print(divsum)

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

ans = 0

# >=74
ans += num(75)

# >=14 & 13~4
ans += num(15)*(num(5)-1)

# >=24 & 23~2
ans += num(25)*(num(3)-1)

# >=4,>=4 & >=2
ans += num(5) * (num(5)-1) * (num(3)-2) // 2 
print(int(ans))

Submission status: Accepted

Solution code:
N=int(input())

e=[0]*(N+1)

for i in range(N+1):
    cur=i
    for j in range(2,cur+1):
        while cur % j==0:
            e[j]+=1
            cur=cur//j
def num(m):
    return(len([i for i in e if i>=m-1]))

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

Submission status: Accepted

Solution code:
N = int(input())
numset = [0]*100
for i in range(N):
  i +=1
  for p in range(2, N+1):
    while i%p == 0:
      numset[p] += 1
      i = i//p
    
niijo = 0
yonijo = 0
juuyonijo =0
nijuuyonijo = 0
nanajuuyonijo =0
for numbers in numset:
  if numbers >= 2: niijo+=1
  if numbers >= 4: yonijo +=1
  if numbers >= 14: juuyonijo +=1
  if numbers >= 24: nijuuyonijo +=1
  if numbers >= 74: nanajuuyonijo+=1
    
count = 0
count += max(0, yonijo*( yonijo-1)*(niijo - 2)//2)
count += max(0, nanajuuyonijo)
count += max(0, (niijo-1)*nijuuyonijo)
count += max(0, (yonijo-1)* juuyonijo)
print(count)

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())
if N<=9:
    print(0)
    exit()

from collections import defaultdict
P = defaultdict(int)

for i in range(2, N+1):
    for p in prime_decomposition(i):
        P[p] += 1

c4 = len([k for k, v in P.items() if v >= 4])
c2 = len([k for k, v in P.items() if v >= 2])
c14 = len([k for k, v in P.items() if v >= 14])
c24 = len([k for k, v in P.items() if v >= 24])
c2 = len([k for k, v in P.items() if v >= 2])
c74 = len([k for k, v in P.items() if v >= 74])


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

Submission status: Accepted

Solution code:
# coding: utf8

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())
kz = [0]*100
for i in range(n):
    # n+1の約数
    t = i + 1
    while True:
        for j in range(2, 11):
            if t % j == 0:
                kz[j] += 1
                t = t // j
                break
        else:
            if t != 1:
                kz[t] += 1
            break
a = 0
for i in range(74):
    a += kz.count(i)
ans = 100 - a
a = 0
for i in range(4):
    a += kz.count(i)
b = 0
for i in range(4, 14):
    b += kz.count(i)
c = 100 - a - b
ans += (c * (c - 1)) + c * b
a = 0
for i in range(2):
    a += kz.count(i)
b = 0
for i in range(2, 24):
    b += kz.count(i)
c = 100 - a - b
ans += (c * (c - 1)) + c * b
a = 0
for i in range(2):
    a += kz.count(i)
b = 0
for i in range(2, 4):
    b += kz.count(i)
c = 100 - a - b
ans += (c * (c - 1) * (c - 2))//2 + (b * c * (c - 1))//2
print(ans)

Submission status: Accepted

Solution code:
N = int(input().strip())

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  # jで割れるなら個数を+1
      cur //= j  # 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 numpy as np

def main():
	n = int(input())
	sosuu = []
	sosuucount = []
	
	for i in range(2, n+1):
		num = i
		sosuuf = 1
		
		for j in range(len(sosuu)):
			if(num % sosuu[j] == 0):
				sosuuf = 0
				while(num % sosuu[j] == 0):
					num /= sosuu[j]
					sosuucount[j] += 1
		if (sosuuf == 1):
			sosuu.append(num)
			sosuucount.append(1)
	num75 = 0
	num25 = 0
	num15 = 0
	num5 = 0
	num3 = 0
	for i in range(len(sosuu)):
		if(sosuucount[i]+1 >= 75):
			num75 += 1
		if(sosuucount[i]+1 >= 25):
			num25 += 1
		if(sosuucount[i]+1 >= 15):
			num15 += 1
		if(sosuucount[i]+1 >= 5):
			num5 += 1
		if(sosuucount[i]+1 >= 3):
			num3 += 1
	r = num75 + num25*(num3-1)+num15*(num5-1) + num5*(num5-1)*(num3-2)/2
	
	print(int(r))
	
	#print(sosuu)
	#print(sosuucount)
	#print(num3, num5, num15, num25, num75)
main()

Submission status: Accepted

Solution code:
def d_756(N):
    def exponential_list(n):
        # ret[k]: nを素因数分解したときのkの指数
        ret = [0] * (n + 1)
        for j in range(2, n + 1):
            current = j
            for k in range(2, j + 1):
                while current % k == 0:
                    ret[k] += 1
                    current //= k
        return ret

    def num(m):
        # Nを素因数分解したときの指数のリスト(e)について、
        # 要素の値がm-1より大きなものの個数
        return len(list(filter(lambda x: x >= m - 1, e)))

    e = exponential_list(N)
    # 素因数のうち、指数が74以上の数を1つ選ぶ。約数の個数の性質より、
    # その数の約数の個数は75以上であるから、約数の個数がちょうど75の数が得られる
    ans = num(75)
    # 指数が24以上の数と3以上の数を1つずつ選ぶと、約数の個数の性質より、
    # それらの数の積における約数の個数は75以上である
    # -1しているのは、指数が2以上の素因数のうち1つを指数が24以上の素因数として
    # (それが存在するならば)選んでいるから
    ans += num(25) * (num(3) - 1)
    ans += num(15) * (num(5) - 1)  # 同上
    # 指数が4以上の素因数を重複して数えている(p^4q^4=q^4p^4)ため、2で割る
    ans += num(5) * (num(5) - 1) * (num(3) - 2) // 2
    return ans

N = int(input())
print(d_756(N))

Submission status: Accepted

Solution code:
import numpy as np

primes = np.array([2,3,5,7,11,13,17,19,23,29,
                   31,37,41,43,47,53,59,61,67,71,73,79,83,97
                  ],dtype=np.int)

def pw(N,p):
    ans = 0
    while N > 0:
        N = N // p
        ans = ans + N
    return ans

N = int(input())
powers = np.vectorize(lambda p: pw(N,p))(primes)

n75 = len(np.where(powers >= 74)[0])
n25 = len(np.where(powers >= 24)[0])
n15 = len(np.where(powers >= 14)[0])
n5 = len(np.where(powers >= 4)[0])
n3 = len(np.where(powers >= 2)[0])

ans75 = n75
ans253 = n25 * (n3-1)
ans553 = ((n5*(n5-1))//2) * (n3-2)
ans515 = n15 * (n5-1)

print(ans75 + ans253 + ans553 + ans515)

Submission status: Accepted

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

N = int(input())

a_list = [0]*100

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

answer = 0

count_2 = len(list(filter(lambda x: x >= 2, a_list)))
count_4 = len(list(filter(lambda x: x >= 4, a_list)))
count_14 = len(list(filter(lambda x: x >= 14, a_list)))
count_24 = len(list(filter(lambda x: x >= 24, a_list)))
count_74 = len(list(filter(lambda x: x >= 74, a_list)))

answer = count_74 + (count_24 * (count_2-1)) + (count_14 * (count_4-1)) + (count_4 * (count_4-1) * (count_2-2))/2

answer = int(answer)
print(answer)

Submission status: Accepted

Solution code:

# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i
    if n > 1:
        yield n

from collections import Counter
from bisect import bisect

N = int(input())
pn = Counter()
for n in range(1,N+1):
    pn.update(prime_factors(n))

pn = sorted(pn.values())

N = len(pn)
cnt = 0
# (3,5,5)
i3 = bisect(pn, 1)
i5 = bisect(pn, 3)
if i5+2 <= N and i3+3 <= N:
    cnt += (N-i3-2) * (N-i5) * (N-i5-1) // 2


# (5,15)
i15 = bisect(pn, 13)
if i15+1 <= N and i5+2 <= N:
    cnt += (N-i15) * (N-i5-1)

    
# (3,25)
i25 = bisect(pn, 23)
if i25+1 <= N and i3+2 <= N:
    cnt += (N-i25) * (N-i3-1)


# (75)
i75 = bisect(pn, 73)
if i75+1 <= N:
    cnt += (N-i75)

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
e = [0]*101

for n in range(2, N+1):
    cur = n
    for i in range(2, n+1):
        while cur%i==0:
            e[i]+=1
            cur //= i

ans = 0
ov74, ov24, ov14, ov4, ov2 = 0,0,0,0,0
for ei in e:
    if ei>=2: ov2 += 1
    if ei>=4: ov4 += 1
    if ei>=14: ov14 += 1
    if ei>=24: ov24 += 1
    if ei>=74: ov74 += 1

ans += ov24*(ov2-1)
ans += ov4*(ov4-1)*(ov2-2)//2
ans += ov14*(ov4-1)
ans += ov74
# print(e)
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools
from collections import defaultdict

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


N = int(input())
# N = 100
anslist = []

primelist = primes(N)

for p in primelist:
    tmp = 0
    i = 1
    while True:
        tmp2 = math.floor(N/(p**i))
        if tmp2 == 0:
            break
        else:
            tmp += tmp2
            i += 1
    anslist.append(tmp)

# print(primelist)
# print(anslist)
# print("------")

ans = []

pqrlist = [[4,4,2],[14,4,0],[24,2,0],[74,0,0]]

combs = list(itertools.permutations(range(len(anslist)), 3))
for pqr in pqrlist:
    for c in combs:
        pp,qq,rr = anslist[c[0]], anslist[c[1]], anslist[c[2]]
        if pp >= pqr[0] and qq >= pqr[1] and rr >= pqr[2]:
            p,q,r = primelist[c[0]], primelist[c[1]], primelist[c[2]]
            product = (p**pqr[0])*(q**pqr[1])*(r**pqr[2])
            if product not in ans:
                ans.append(product)

print(len(ans))