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: Time Limit Exceeded

Solution code:
class Factorization:	
	def __init__(self):
		# privateなインスタンス変数を作成
		self.__factors = dict()
		self.__n = 0
	
	
	def get_factors(self, n):
		# [summary] 素因数分解した結果を、辞書([素因数, 指数]...)で返す
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			# 2より小さい数の場合、素因数分解できない
			return { n:1 }
		else:
			self.__factorization()
			
			return self.__factors
	
	
	def get_divisors(self, n):
		# [summary] 約数をリストに列挙
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			return [1]
		else:
			self.__factorization()
			divisors = [1]
			
			for k, v in self.__factors.items():
				import copy
				copy_ = copy.deepcopy(divisors)
								
				for i in range(1, v + 1):
					for c in copy_:
						divisors.append(c * (k ** i))
			
			return divisors

				
	def count_divisors(self, n):
		# [summary] 約数の個数を返す
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			return 1
		else:
			self.__factorization()
			count = 1
			
			for v in self.__factors.values():
				count *= v + 1
			
			return count
	

	def	__factorization(self):
		# [summary]素因数分解した結果を、インスタンス変数に格納
		
		# 2,3,5で、割れなくなるまで割り続ける
		# (末尾に2,3,5のつく数は素数でないことが明白なので
		# 後続の処理で素数のリストに入れないように、先に処理する)
		self.__divide_with(2)
		self.__divide_with(3)
		self.__divide_with(5)
			
		# 平方根以下の素数で総当たりで試し割りする
		# (実際は、素数らしき数)
		import math
		sqrt_ = math.floor(math.sqrt(self.__n))
			
		primes = [7, 11, 13, 17, 19, 23, 29, 31]
		i = 0
		is_break = False
			
		while self.__n > 1:
			for p in primes:
				if p + i <= sqrt_:
					self.__divide_with(p + i)
				else:
					# 試し割りする数が平方根を超えたら、ループを抜ける
					is_break = True
						
					# 1が素因数に追加されることを防止
					if self.__n > 1:
						self.__factors.setdefault(self.__n, 1)
				
			if is_break:
				break
			else:
				i += 30
	
	
	def __divide_with(self, d):
		count = 0
		
		while self.__n % d == 0:
			self.__n //= d
			count += 1
		
		if count > 0:
			self.__factors.setdefault(d, count)


# D - 756
n = int(input())

lib = Factorization()
factors = dict()

for i in range(2, n + 1):
	for k, v in lib.get_factors(i).items():
		factors.setdefault(k, 0)
		factors[k] += v

divisors = [1]

for k, v in factors.items():
	import copy
	copy_ = copy.deepcopy(divisors)

	for i in range(1, v + 1):
		for c in copy_:
			divisors.append(c * (k ** i))

ans = 0

for d in divisors:
	if len(lib.get_divisors(d)) == 75:
		ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

def fac(x):
    L74=L24=L14=L4=L2=0
    num=x
    for i in range(2,int(-((-x**0.5)//1)+1)):
        if num%i==0:
            cnt=0
            while num%i==0:
                cnt += 1
                num //= i
            if cnt>=2:
                L2+=1
            if cnt>=4:
                L4+=1
            if cnt>=14:
                L14+=1
            if cnt>=24:
                L24+=1
            if cnt>=74:
                L74+=1
    return [L2,L4,L14,L24,L74]
m=fac(n)

ans=m[4]+m[3]*(m[0]-1)+m[2]*(m[1]-1)+m[1]*(m[1]-1)*(m[0]-2)/2
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from functools import reduce
from operator import mul
from math import factorial

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

def prime_factorize(n):
  factors = {}
  for i in range(2,n+1):
    while n%i ==0:
      n /= i
      if i not in factors:
        factors[i] = 1
      else:
        factors[i] += 1
  return factors

N = int(input())
ans = 0
for div in make_divisors(factorial(N)):
  res = prime_factorize(div)
  if len(res) > 0:
    div_num = reduce(mul, [num+1 for num in res.values()])
    if div_num == 75: ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from functools import reduce
from operator import mul
from math import factorial

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

def prime_factorize(n):
  divs = []
  for i in range(2,n+1):
    while n%i ==0:
      n /= i
      divs.append(i)
  return divs

N = int(input())
ans = 0
for div in make_divisors(factorial(N)):
  res = prime_factorize(div)
  if len(res) > 0:
    div_num = reduce(mul, [num+1 for num in Counter(res).values()])
    if div_num == 75: ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

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

    return True
plist = []
p = 0
for i in range(100):
    if (is_prime(i+1)):
        plist.append(i+1)
        p += 1
clist = [0]*p
n = int(input())
o = 1
for i in range(n):
    o *= i+1
a = 1
b = 1
c = 0
ans = 1
while True:
    if a**2 > o:
        break
    elif o%a**2 != 0:
        b+=1
        a = b
        continue
    for i in range(p):
        while a%plist[i] == 0:
            a /= plist[i]
            clist[i] += 1
    for i in range(p):
        ans *= 2*clist[i] + 1
    if ans == 75:
        c+=1
    b+=1
    a = b
    ans = 1
    clist = [0]*p
print(c)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

def primes(m) :
    ps = [2]
    for i in range(3, m) :
        for p in ps :
            if i%p == 0 :
                break
        else :
            ps.append(i)
    return ps

def fdivisor(m) :
    ps = primes(m)
    df = {p:0 for p in ps}
    for i in range(1, m+1) :
        ii = i
        while ii != 1 :
            for p in ps :
                if ii%p == 0 :
                    df[p] += 1
                    ii //= p
    return df

ans = 0
df = fdivisor(n)
over2 = len([v for v in df.values() if v >= 2])
over4 = len([v for v in df.values() if v >= 4])
over14 = len([v for v in df.values() if v >= 14])
over24 = len([v for v in df.values() if v >= 24])
over74 = len([v for v in df.values() if v >= 74])
ans += over4*(over4-1)//2*(over2-2)
ans += over14*(over4-1)
ans += over24*(over2-1)
ans += over74

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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 counter(n):
    import math
    
    if n==0:
        return 0
    else:
        lst = list(set(make_divisors(math.factorial(n)))-set(make_divisors(math.factorial(n-1))))
        return counter(n-1)+sum([len(make_divisors(i))==75 for i in lst])
    
print(counter(N))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import itertools
from  bisect import bisect_left, bisect_right

N=input()

Parts=defaultdict(lambda: 0)

for i in range(1,N+1):
	num_sqrt=int(i**0.5)+2

	for n in range(2,num_sqrt):
		while i%n==0:
			i/=n
			Parts[n]+=1
	else:
		if i!=1:
			Parts[i]+=1

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


L=[]
for x in Parts.values():
	bi=bisect_right(T,x)
	L.append( T[:bi] )
	

K=list(itertools.product(*L))	#Kouho

ans=0
for x in K:
	multiple=1
	for v in x:
		multiple*=(v+1)
	if multiple==75:
		ans+=1


print ans

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import itertools

N=input()

Parts=defaultdict(lambda: 0)

for i in range(1,N+1):
	num_sqrt=int(i**0.5)+2

	for n in range(2,num_sqrt):
		while i%n==0:
			i/=n
			Parts[n]+=1
	else:
		if i!=1:
			Parts[i]+=1

L=[]
for x in Parts.values():
	L.append( range(x+1) )


K=list(itertools.product(*L))	#Kouho

ans=0
for x in K:
	multiple=1
	for v in x:
		multiple*=(v+1)
	if multiple==75:
		ans+=1


print ans

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

elem = [0 for _ in range(N+1)]

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import math
p=math.factorial(n)  
q=int(math.sqrt(p)//1)
count=0
for i in range(1,q+1):
  if p % (i**2) == 0:
    a=0
    for j in range(1,i):
      if (i**2) % j == 0:
        a+=1
    if a==37:
      count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import math
p=1
for i in range(1,n+1):
  p=p*i
q=int(math.sqrt(p)//1)
count=0
for i in range(38,q+1):
  if p % (i**2) == 0:
    a=0
    for j in range(1,i):
      if (i**2) % j == 0:
        a+=1
    if a==37:
      count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import math
p=1
for i in range(1,n+1):
  p=p*i
q=int(math.sqrt(p)//1)
count=0
for i in range(1,q+1):
  if p % (i**2) == 0:
    a=0
    for j in range(1,i):
      if (i**2) % j == 0:
        a+=1
    if a==37:
      count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import Counter
import itertools

def prime_factors(n):
  i = 2
  factors = []
  while i * i <= n:
    if n % i==0:
      n //= i
      factors.append(i)
    else:
      i += 1
  if n > 1:
    factors.append(n)
  return factors

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

n=int(input())
num=math.factorial(n)
yakusu=make_divisors(num)

cnt=0
for i in yakusu:
  factors=list(map(lambda x:x+1,Counter(prime_factors(i)).values()))
  tmp=1
  for j in factors:
    tmp*=j
  if tmp==75:
    cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
primes = [2]
for i in range(3, 100):
    flag = True
    for j in primes:
        if i%j==0:
            flag = False
            break
    if flag:
        primes.append(i)

factors = [0 for i in range(len(primes))]
def mul(x):
    if x==2:
        factors[0] += 1
        return 2
    else:
        tmp = x
        while tmp != 1:
            for i, prime in enumerate(primes):
                if tmp%prime==0:
                    factors[i] += 1
                    tmp = tmp//prime
                    break

        return x*mul(x-1)

mul(n)
num74 = 0
num24 = 0
num14 = 0
num4 = 0
num2 = 0
for factor in factors:
    if factor>=74:
        num74 += 1
    elif factor>=24:
        num24 += 1
    elif factor>=14:
        num14 += 1
    elif factor>=4:
        num4 += 1
    elif factor >=2:
        num2 += 1

ans = 0
''' 3 * 5 * 5 '''
tmp1 = num74+num24+num14+num4
tmp2 = num2
ans += tmp1*(tmp1-1)//2*tmp2 + tmp1*(tmp1-1)//2*(tmp1-2)
''' 5 * 15 '''
tmp1 = num74+num24+num14
tmp2 = num4
ans += tmp1*tmp2 + tmp1*(tmp1-1)
''' 3 * 25 '''
tmp1 = num74+num24
tmp2 = num14+num4+num2
ans += tmp1*tmp2 + tmp1*(tmp1-1)
''' 75 '''
tmp1 = num74
ans += tmp1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools as t
n = [i+1 for i in range(int(input()))]
x = []
for i in range(len(n)-1):
    x += list(t.combinations(n,i+1))
for i in range(len(x)):
    x[i] = np.array(x[i])
    x[i] = x[i].prod()
x = list(set(x))
y = []
for i in x:
    count = 0
    for j in range(1, i+1):
        if i % j == 0:
            count += 1
    y.append(count)
print(y.count(75))

Submission status: Time Limit Exceeded

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

from math import factorial, sqrt

# 約数の個数
def num_div(num):
    total = 1
    # 終点はルート切り捨て+1
    end = int(sqrt(num)) + 1
    for i in range(2, end+1):
        cnt = 0
        # 素因数分解：小さい方から割れるだけ割って指数をカウント
        while num % i == 0:
            num //= i
            cnt += 1
        # 指数+1をかけていくと約数をカウントできる
        total *= (cnt + 1)
        # 最後までそのまま来たやつは素数なので2つ
        if i == end and total == 1:
            return 2
    return total

# 約数の列挙
def num_div_set(N):
    # 1とその数はデフォで入れとく
    s = {1, N}
    # 終点はルート切り捨て+1
    end = int(sqrt(N)) + 1
    for i in range(2, end+1):
        # 割り切れるなら、iとN/iを追加
        if N % i == 0:
            s.add(i)
            s.add(N // i)
    return s

N = int(input())

num = factorial(N)

cnt = 0
for i in num_div_set(num):
        if num_div(i) == 75:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math

N = math.factorial(int(input()))
yakusu = []

for i in range(1,round(math.sqrt(N))+1):
    if N % i == 0:
        if isinstance(round(math.sqrt(i)), int) == True:
            yakusu.append(i)
        if isinstance(round(math.sqrt(N//i)), int) == True:
            yakusu.append(N // i)

nagomi = []

for i in yakusu:
    cnt = 1
    for j in range(1,round(math.sqrt(i))):
        if i % j == 0:
                   cnt += 2
    if cnt == 75:
        nagomi.append(i)

print(len(nagomi))

Submission status: Time Limit Exceeded

Solution code:
import math


def num_divisors(n):
    num = 0
    for i in range(1,int(n**0.5)+1):
        if n % i == 0:
            num += 1
            if n != i**2:
                num += 1
    return num


def divisors(n):
    res = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            res.append(i)
            res.append(n//i)
    return res


n = int(input())
n_dash = math.factorial(n)

# yakusuu = [i for i in range(75, n_dash+1) if n_dash%i==0]
# yakusuu = []
yakusuu = divisors(n_dash)

ans = 0
n_yakusuu = list(map(num_divisors, yakusuu))
print(n_yakusuu.count(75))

Submission status: Time Limit Exceeded

Solution code:

import sys
import math

def kansu(a):

    cnt = 1
    for j in range(1,a):
        
        if a % j == 0:
            cnt = cnt + 1
    #print(cnt)
    
    return cnt


num = int(input())

kazu = math.factorial(num)

ans = 0

for i in range(1,kazu):
    if kazu % i == 0:
        kosu = kansu(i)

        if kosu ==75:
            ans = ans + 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def fact(n, _factcache={}):
    if n not in _factcache:
        _factcache[n] = math.factorial(n)
    return _factcache[n]

def divisorGenerator(n):
    large_divisors = []
    for i in range(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            yield i
            if i*i != n:
                large_divisors.append(n / i)
    for divisor in reversed(large_divisors):
        yield divisor


def fiveSeven(n):
    counter = 0
    divisors = list(divisorGenerator(fact(n)))
    for _, divisor in enumerate(divisors):
        if len(list(divisorGenerator(divisor))) == 75:
            counter += 1
    return counter

i = int(input())
print(fiveSeven(i))

Submission status: Time Limit Exceeded

Solution code:
import math

def fact(n):
    if n > 0:
        result = n * fact(n - 1)
        return result
    else:
        return 1

def divisorGenerator(n):
    large_divisors = []
    for i in range(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            yield i
            if i*i != n:
                large_divisors.append(n / i)
    for divisor in reversed(large_divisors):
        yield divisor


def fiveSeven(n):
    counter = 0
    divisors = list(divisorGenerator(fact(n)))
    for _, divisor in enumerate(divisors):
        if len(list(divisorGenerator(divisor))) == 75:
            counter += 1
    return counter

i = int(input())
print(fiveSeven(i))

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())

def factorization(n):
    def factor_sub(n, m):
        c = 0
        while n % m == 0:
            c += 1
            n /= m
        return c, n
    buff = []
    c, m = factor_sub(n, 2)
    if c > 0:
        buff.append((2, c))
    c, m = factor_sub(m, 3)
    if c > 0:
        buff.append((3, c))
    x = 5
    while m >= x * x:
        c, m = factor_sub(m, x)
        if c > 0:
            buff.append((x, c))
        if x % 6 == 5:
            x += 2
        else:
            x += 4
    if m > 1:
        buff.append((m, 1))
    return buff


def divisor_num(n):
    a = 1
    for _, x in factorization(n):
        a *= x + 1
    return a

def div_list(X):
    div = []
    for i in range(1, int(math.sqrt(X)+1)):
        if X % i == 0:
            div.append(i)
            if i != X//i:
                div.append(X//i)
    return div


X = math.factorial(N)
div = div_list(X)
# 約数の列挙

ans = 0
for i in div:
    if divisor_num(i) == 75:
        ans += 1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def func1(target):
  list = []
  for i in range(1, target+1):
    if target % i == 0:
      list.append(i)
  
  return len(list) == 75


def func2(target):
  for i in range(1, target+1):
    if target % i == 0:
      yield i


def func3(target):
  return math.factorial(target)


result = 0
input = int(input())

tage = func3(input)

for i in func2(tage):
  if func1(i):
    result += 1

print(result)

Submission status: Time Limit Exceeded

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

import time

# start = time.time()

# N = 10
N = int(input())

def yakusu_list(n):
    output = []
    for i in range(1, n//2 + 1):
        if n % i == 0:
            output.append(i)

    output.append(n)

    return output


def comb(x, rest_list, output_list):
    if len(rest_list) > 0:
        hs = rest_list[0]
        for h in hs:
            comb(h * x, rest_list[1:len(rest_list)], output_list)
    else:
        output_list.append(x)

    return output_list


def clean_list(l):
    l = sorted(l)

    output = [1]
    for num in l:
        if output[-1] != num:
            output.append(num)

    return output


# a = comb(1, [[1,2], [1,3], [1,2,4]], [])

N_list = []
for i in range(1, N + 1):
    N_list.append(yakusu_list(i))

yakusu = clean_list(comb(1, N_list, []))
# print(N_list)
# print(clean_list(comb(1, N_list, [])))

cnt = 0
for i in yakusu:
    if len(yakusu_list(i)) == 75:
        # print(i)
        cnt += 1

print(cnt)
# print(time.time() - start)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

count = 0
if 10 <= N:

    num = 1
    for i in range(2,N+1):
        num *= i
    num_array = []
    for i in range(1,num+1):
        if num % i == 0:
            num_array.append(i)

    for i in num_array:
        array = []
        for j in range(1,i+1):
            if i % j == 0:
                array.append(j)
        if len(array) == 75:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:

import sys
import math

def kansu(a):

    yakusuu_array = []
    
    for i in range(1,a):
        if a % i == 0:
            yakusuu_array.append(i)
    ko = len(yakusuu_array) + 1
    return ko


num = int(input())

kazu = math.factorial(num)

#num = int(sys.argv[1])
#print(kazu)

yakusuu_array1 = []

for i in range(1,kazu):
    if kazu % i == 0:
        yakusuu_array1.append(i)

    #print(i)
    
#print(yakusuu_array1)

k = len(yakusuu_array1)

ans = 0

for j in range(k):

    kosu = kansu(yakusuu_array1[j])

    #print(kosu)
    
    if kosu ==75:
        ans = ans + 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
fac = math.factorial(N)


yaku_list = []
for i in range(1,fac+1) :
	if (fac % i == 0) :
		yaku_list.append(i)

count = 0
for y in yaku_list :
	c = 0
	for i in range(1,y+1) :
		if (y % i == 0) :
			c += 1

	if (c == 75) :
		count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
n = factorial(int(input()))
ny = [i for i in range(1,n+1) if n % i == 0]
ans = [len([k for k in range(1,j+1) if j % k == 0]) for j in ny]
print(ans.count(75))

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())

a = 1

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

#print(a)

def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]


def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)

        return divisor_list

y = make_divisor_list(a)

def search_divisor_num_1(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num

ans = 0

for yk in y:
   d  = search_divisor_num_1(yk)
   if d == 75:
       ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from math import factorial

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 prime_factoring(n):
    from collections import Counter
    a = prime_factorize(n)
    return Counter(a)

N = int(input())
fac =factorial(N)
List = prime_factoring(fac).values()
# print(List)

def num(m):
    return len(list(filter(lambda x: x >= m-1, List)))
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^74 p^2q^24 p^2q^4r^4 p^4q^14 
# 2^74 q=2,3,5           q=2,3,5,7,
#3 5 5
#75,5 15,3 25,3 5 5 
from collections import defaultdict
memo=defaultdict(lambda:-1)

def f(x):
    if memo[x]!=-1:return memo[x]
    ret=0;temp=n
    while temp:
        temp//=x
        ret+=temp
    memo[x]=ret
    return ret
ans=0
primes=[2,3]
for i in range(5,101,6):
    for p in primes:
        if i%p:continue
        break
    else:primes.append(i)
    i+=2
    for p in primes:
        if i%p:continue
        break
    else:primes.append(i)
di=[i**2 for i in primes]
qu=[j**2 for j in di]
for p in primes:
    if f(p)>=74:ans+=1
    else:break
def g(a,b):
    global ans
    for p in primes:
        if f(p)>=a:
            for q in primes:
                if f(q)>=b:
                    if q!=p:ans+=1
                    else:continue
        else:break
    return 0
g(2,24)
g(4,14)

for q in range(len(qu)):
    for r in range(q+1,len(qu)):
        a,b=qu[q],qu[r]
        if not (f(primes[q])>=4 and f(primes[r])>=4):continue
        for i,d in enumerate(di):
            if d**2 not in {a,b} and f(primes[i])>=2:ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

def main():
    N = int(input())
    d = defaultdict(int)
    for i in range(1,N+1):
        for j in prime_factor(i):
            d[j] += 1
    # 1 * 75
    # 3 * 25
    # 5 * 15
    # 3 * 5 * 5
    e = defaultdict(int)
    for i, j in d.items():
        if j >= 2:
            e[2] += 1
        if j >= 4:
            e[4] += 1
        if j >= 14:
            e[14] += 1
        if j >= 24:
            e[24] += 1
        if j >= 74:
            e[74] += 1
    ans = 0
    ans += (e[2] - 1) * e[24]
    ans += (e[4] - 1) * e[14]
    ans += e[74]
    ans += (e[2] - 2) * e[4] * (e[4] - 1) // 2
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())

l = []
for i in range(1, N+1):
  while i % 2 == 0:
    l.append(2)
    i //= 2
  f = 3
  while f * f <= i:
    if i % f == 0:
      l.append(f)
      i //= f
    else:
      f += 2
  if i != 1:
    l.append(i)

c = Counter(l)
m = c.most_common()
c_75, c_25, c_15, c_5, c_3 = 0, 0, 0, 0, 0
for a in m:
  if a[1] >= 74:
    c_75 += 1
  if a[1] >= 24:
    c_25 += 1
  if a[1] >= 14:
    c_15 += 1
  if a[1] >= 4:
    c_5 += 1
  if a[1] >= 2:
    c_3 += 1
    
ans = c_75
ans += c_25 * (c_3-1)
ans += c_15 * (c_5-1)
ans += (c_5*(c_5-1)//2) * (c_3-2)
print(ans)

Submission status: Accepted

Solution code:
import math
n=int(input())
p=[0]*101
dp=[0]*101
for i in range(2,n+1):
  for j in range(2,i+1):
    while i%j==0:
      i//=j
      p[j]+=1
for i in range(101):
  if p[i]!=0:
    dp[p[i]]+=1
ans=sum(dp[74:])+sum(dp[24:])*(sum(dp[2:])-1)+sum(dp[14:])*(sum(dp[4:])-1)+sum(dp[4:])*(sum(dp[4:])-1)//2*(sum(dp[2:])-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:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque

def prime_factorization(x):
    """素因数分解"""
    import math
    re = []
    i = 2
    while x != 1:
        if x % i == 0:
            re.append(i)
            x //= i
        else:
            i += 1
            if i > math.sqrt(x):
                re.append(x)
                break
    return re


# from decorator import stop_watch
#
#
# @stop_watch
def solve(N):
    pf = []
    for i in range(1, N + 1):
        pf += prime_factorization(i)
    pf_nums = [0] * (N + 1)
    for p in pf:
        pf_nums[p] += 1

    def num(m):
        return len([i for i in pf_nums if i >= m - 1])

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

    print(ans)


if __name__ == '__main__':
    N = int(input())
    solve(N)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque

def prime_factorization(x):
    """素因数分解"""
    import math
    re = []
    i = 2
    while x != 1:
        if x % i == 0:
            re.append(i)
            x //= i
        else:
            i += 1
            if i > math.sqrt(x):
                re.append(x)
                break
    return re


def cmb(n, r):
    """組み合わせ"""
    import math
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N):
    pf = []
    for i in range(1, N + 1):
        pf += prime_factorization(i)
    pf_num = {}
    for p in pf:
        pf_num.setdefault(p, 0)
        pf_num[p] += 1
    over2 = 0
    over4 = 0
    over14 = 0
    over24 = 0
    over74 = 0
    for v in pf_num.values():
        if 74 <= v:
            over74 += 1
        if 24 <= v:
            over24 += 1
        if 14 <= v:
            over14 += 1
        if 4 <= v:
            over4 += 1
        if 2 <= v:
            over2 += 1
    ans = 0
    # 3-5-5
    ans += (over2 - over4) * cmb(over4, 2)
    ans += cmb(over4, 3) * 3

    # 5-15
    ans += (over4 - over14) * over14
    ans += cmb(over14, 2) * 2

    # 3-25
    ans += (over2 - over24) * over24
    ans += cmb(over24, 2) * 2

    # 75
    ans += over74

    print(ans)


if __name__ == '__main__':
    N = int(input())
    solve(N)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

Submission status: Accepted

Solution code:
import itertools

n=int(input())

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

a=[]
for i in range(2,n+1):
    aa=prime_decomposition(i)
    a.extend(aa)
    
a.sort()

i75=0
i25=0
i15=0
i5=0
i3=0
gr = itertools.groupby(a)
for key, group in gr:
    ll=len(list(group))
#    print(ll)
    if ll>=74:
        i75+=1
    if ll>=24:
        i25+=1
    if ll>=14:
        i15+=1
    if ll>=4:
        i5+=1
    if ll>=2:
        i3+=1
ans=0
ans=ans+i75
ans=ans+i25*max(i3-1,0)
ans=ans+i15*max(i5-1,0)
ans=ans+i5*max(i5-1,0)*max(i3-2,0)//2
print(ans)

Submission status: Accepted

Solution code:
# 

def factorize(n):
    '''
    タプルの配列と思ったけど逐次割り算する過程で次数を増やせないじゃん。
    二重配列?
    dictにしよう。
    '''
    if n == 1:
        raise('n >= 2')
    
    factor = {}
    div = 2
    while True:
        if n % div == 0:
            n //= div
            factor[div] = factor.get(div, 0) + 1
            if n == 1:
                return factor
        else:
            div += 1

n = int(input())

if n <= 9:
    print(0)
    exit()

# めんどいから掛けてしまえ。間に合うだろ
import math
product = math.prod(range(1, n+1))
d = factorize(product)
factor = list(d.items())

# print(factor)

ans = 0
for i in range(len(factor)):
    for j in range(i+1, len(factor)):
        for k in range(len(factor)):
            if factor[i][1] >= 4 and factor[j][1] >= 4 and factor[k][1] >= 2 and i!=j and j!=k and k!=i:
                ans += 1

for i in range(len(factor)):
    for j in range(len(factor)):
            if factor[i][1] >= 4 and factor[j][1] >= 14 and i!=j:
                ans += 1

for i in range(len(factor)):
    for j in range(len(factor)):
            if factor[i][1] >= 2 and factor[j][1] >= 24 and i!=j:
                ans += 1

for i in range(len(factor)):
    if factor[i][1] >= 74:
                ans += 1

print(ans)

Submission status: Accepted

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

n=int(input())
x=[0]*(n+1)
for i in range(1,n+1):
  for j in num_div(i):
    x[j]+=1
ex2=len([i for i in x if i>1])
ex4=len([i for i in x if i>3])
ex14=len([i for i in x if i>13])
ex24=len([i for i in x if i>23])
ex74=len([i for i in x if i>73])
print(ex4*(ex4-1)//2*(ex2-2)+ex24*(ex2-1)+ex14*(ex4-1)+ex74)