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:
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]
prime_count = {}
n = int(input())

for i in range(1, n + 1):
    for prime in primes:
        if i < prime:
            break
        devided = i
        while devided % prime == 0:
            prime_count[prime] = prime_count.get(prime) + 1 if prime_count.get(prime) else 1
            devided /= prime

primes_2 = []
primes_4 = []
primes_14 = []
primes_24 = []
primes_74 = []
for k, v in prime_count.items():
    if v >= 74:
        primes_74.append(k)
    if v >= 24:
        primes_24.append(k)
    if v >= 14:
        primes_14.append(k)
    if v >= 4:
        primes_4.append(k)
    if v >= 2:
        primes_2.append(k)

count = 0

# a**2 * b**4 * c**4
count_primes_4 = len(primes_4)
for prime_2 in primes_2:
    if prime_2 in primes_4 and count_primes_4 >= 3:
        count += ((count_primes_4 - 1) * (count_primes_4 - 2)) // 2
    if prime_2 not in primes_4 and count_primes_4 >= 2:
        count += ((count_primes_4) * (count_primes_4 - 1)) // 2

# a**4 * b**14
count_primes_14 = len(primes_14)
for prime_4 in primes_4:
    if prime_4 in primes_14:
        count += count_primes_14 - 1
    else:
        count += count_primes_14

# a**2 * b**24
count_primes_24 = len(primes_24)
for prime_2 in primes_2:
    if prime_2 in primes_24:
        count += count_primes_24 - 1
    else:
        count += count_primes_24

# a**74
count += len(primes_74)

print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main2():
    dic = {1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0, 10:1, 11:1, 12:1, 13:1, 14:2, 15:2, 16:3, 17:3, 18:3, 19:3, 20:8, 21:8, 22:11, 23:11, 24:11, 25:11, 26:14, 27:14, 28:32, 29:32, 30:35, 31:35, 32:35, 33:35, 34:42, 35:42, 36:42, 37:42, 38:49, 39:49, 40:49, 41:49, 42:49, 43:49, 44:75, 45:75, 46:86, 47:86, 48:86, 49:86, 50:86, 51:86, 52:123, 53:123, 54:131, 55:131, 56:131, 57:131, 58:148, 59:148, 60:153, 61:153, 62:170, 63:170, 64:170, 65:170, 66:170, 67:170, 68:227, 69:227, 70:227, 71:227, 72:227, 73:227, 74:250, 75:250, 76:323, 77:323, 78:324, 79:324, 80:324, 81:324, 82:354, 83:354, 84:354, 85:354, 86:384, 87:384, 88:384, 89:384, 90:384, 91:391, 92:491, 93:491, 94:529, 95:529, 96:529, 97:529, 98:529, 99:529, 100:543}
    print(dic[int(input())])


if __name__ == '__main__':
    main2()

Submission status: Accepted

Solution code:

from collections import defaultdict

def get_yakusuu(num):
    yakusuu_dic = defaultdict(int)
    seed_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]
    for now_num in range(1, num + 1):
        for num_ele in seed_primes:
            if now_num < num_ele:
                break
            while now_num % num_ele == 0:
                yakusuu_dic[num_ele] += 1
                now_num = now_num // num_ele
    return list(yakusuu_dic.values())

def calc(yakusuu_dic, lim):
    count = 0
    for num in yakusuu_dic:
        if num >= lim:
            count += 1
        else:
            break
    return count

def main():
    num = int(input())
    yakusuu_dic = get_yakusuu(num)
    yakusuu_dic.sort(reverse=True)

    up_4 = calc(yakusuu_dic, 4)
    up_2 = calc(yakusuu_dic, 2)
    ans1 = max(up_4 * (up_4 - 1) * (up_2 - 2) // 2, 0)

    up_24 = calc(yakusuu_dic, 24)
    ans2 = max(up_24 * (up_2 - 1), 0)

    up_14 = calc(yakusuu_dic, 14)
    ans3 = max(up_14 * (up_4 - 1), 0)

    up_74 = calc(yakusuu_dic, 74)
    ans4 = up_74

    ans = ans1 + ans2 + ans3 + ans4

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
p = [0]*(n+1)
for i in range(2,n+1):
    for j in range(2,n+1):
        while i%j == 0:
            p[j] += 1
            i //= j
a,b,c,e,d = 0,0,0,0,0
for prime in p:
    if prime >= 74:
        a += 1
    if prime >= 24:
        b += 1
    if prime >= 14:
        c += 1
    if prime >= 4:
        d += 1
    if prime >= 2:
        e += 1
print(a+b*(e-1)+c*(d-1)+(e-2)*d*(d-1)//2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import itertools
from operator import mul
from functools import reduce


N = int(input())
F = 1
for i in range(1,N+1):
    F = F*i

pns = []
for n in range(2, N+1):
    for pn in pns:
        if n % pn == 0:
            break
    else:
        pns.append(n)
c = 0
for num in pns:
    if F % num**74 == 0:
        c += 1
for nums in itertools.combinations(pns, 2):
    y1 = nums[0]**14 * nums[1]**4
    y2 = nums[1]**14 * nums[0]**4
    z1 = nums[0]**24 * nums[1]**2
    z2 = nums[1]**24 * nums[0]**2
    if F % y1 == 0:
        c += 1
    if F % y2 == 0:
        c += 1
    if F % z1 == 0:
        c += 1
    if F % z2 == 0:
        c += 1
for nums in itertools.combinations(pns, 3):
    for num in nums:
        num_except = [n for n in nums if n != num]
        x = num**2 * (num_except[0]*num_except[1])**4
        if F % x == 0:
            c += 1
print(c)

Submission status: Accepted

Solution code:
import itertools
from collections import Counter

n = int(input())

# 素因数分解した結果のリスト
# {1: [], 2: [2], 3: [3], 4: [2, 2], 5: [5]}
divs = {}
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]

for i in range(1, n + 1):
    divs[i] = []
    x = i
    while x >= 2:
        for p in primes:
            if x % p == 0:
                x //= p
                divs[i].append(p)

# flatten
fdivs = list(itertools.chain.from_iterable(divs.values()))
counts = Counter(fdivs)

ans = 0
# 75==5*5*3
# https://juken-mikata.net/how-to/mathematics/number-of-divisor.html
# 4, 4, 2 選んだら75数になる
ge4 = len([c for c in counts.values() if c >= 4])
ge2 = len([c for c in counts.values() if c >= 2])
ans += ge4 * (ge4 - 1) / 2 * (ge2 - 2)

# 75==5*15
# 4, 14 選ぶ
ge14 = len([c for c in counts.values() if c >= 14])
ans += ge14 * (ge4 - 1)

# 75==25*3
# 24, 2 選ぶ
ge24 = len([c for c in counts.values() if c >= 24])
ans += ge24 * (ge2 - 1)

# 75 ==75*1
# 74 選ぶ
ge74 = len([c for c in counts.values() if c >= 74])
ans += ge74

print(int(ans))

Submission status: Accepted

Solution code:
import bisect
from math import factorial as fact
import sys
input = sys.stdin.readline
 
N = int(input())
prime = []
p_flag = [False] * (101)
p_flag[0] = p_flag[1] = True
 
for i in range(2, 101):
    if not p_flag[i]:
        prime.append(i)
        for j in range(2*i, 101, i):
            p_flag[j] = True
 
M = len(prime)
factor = [0]*M
 
for i in range(2, N+1):
    for j in range(M):
        tmp = prime[j]
        if tmp > i:
            break
        while i % tmp == 0:
            factor[j] += 1
            tmp *= prime[j]
 
factor = factor[::-1]
point74 = M - bisect.bisect_left(factor, 74)
point24 = M - bisect.bisect_left(factor, 24)
point14 = M - bisect.bisect_left(factor, 14)
point4 = M - bisect.bisect_left(factor, 4)
point2 = M - bisect.bisect_left(factor, 2)
 
if N < 10:
    ans = 0
else:
    ans = fact(point4)//(fact(point4-2)*fact(2)) * (point2-2)
    if point14 > 0:
        ans += point14 * (point4-1)
    if point24 > 0:
        ans += point24 * (point2-1)
    if point74 > 0:
        ans += point74
 
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
import collections
import itertools
INF = float("inf")


def trial_division_sqrt(n):
    prime_count = collections.Counter()

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

    return prime_count


def eratosthenes_sieve(n):
    table = [0] * (n + 1)
    prime_list = []

    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1

    return prime_list


def solve(N: int):
    primes = eratosthenes_sieve(N)

    pc = collections.Counter()
    for n in range(1, N+1):
        pc += trial_division_sqrt(n)
    ans = 0

    for p in itertools.combinations(primes, 3):
        # 2 4 4
        if pc[p[0]] >= 2 and pc[p[1]] >= 4 and pc[p[2]] >= 4:
            ans += 1
        # 4 2 4
        if pc[p[0]] >= 4 and pc[p[1]] >= 2 and pc[p[2]] >= 4:
            ans += 1
        # 4 4 2
        if pc[p[0]] >= 4 and pc[p[1]] >= 4 and pc[p[2]] >= 2:
            ans += 1

    for p in itertools.combinations(primes, 2):
        # 2 24
        if pc[p[0]] >= 2 and pc[p[1]] >= 24:
            ans += 1
        # 24 2
        if pc[p[0]] >= 24 and pc[p[1]] >= 2:
            ans += 1

        if pc[p[0]] >= 4 and pc[p[1]] >= 14:
            ans += 1
        if pc[p[0]] >= 14 and pc[p[1]] >= 4:
            ans += 1

    for p in primes:
        if pc[p] >= 74:
            ans += 1

    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == '__main__':
    main()

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,i+1):
        while cur%j==0:
            e[j]+=1
            cur=cur//j

def num(m):
    tmp=0
    for i in range(N+1):
        if e[i]>=m:
            tmp+=1
    return tmp

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

Submission status: Accepted

Solution code:
N=int(input())
pdic={2:0}
for i in range(3,50,2):
    for j in pdic.keys():
        if i%j==0:
            break
    else:
        pdic[i]=0
for i in range(2,N+1):
    for p in pdic.keys():
        while i%p==0:
            pdic[p]+=1
            i//=p
ge={i:sum(x>=i-1 for x in pdic.values()) for i in (3,5,15,25,75)}
if ge[5]<2 and ge[3]<3:
    print(0)
else:
    print(ge[5]*(ge[5]-1)//2*(ge[3]-2)+ge[25]*(ge[3]-1)+ge[15]*(ge[5]-1)+ge[75])

Submission status: Accepted

Solution code:
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]

def get_prime(n, count = {p: 0 for p in primes}):
    for p in primes:
        cp = n
        while cp != 0 and cp % p == 0:
            count[p] += 1
            cp = cp // p
    return count

cnt = {p: 0 for p in primes}
for i in range(1, int(input())+1):
    get_prime(i, cnt)

res = 0
for p1 in primes:
    if cnt[p1] >= 4:
        for p2 in primes:
            if cnt[p2] >= 4 and p1 > p2:
                for p3 in primes:
                    if cnt[p3] >= 2 and p3 != p1 and p3 != p2:
                        res += 1

for p1 in primes:
    if cnt[p1] >= 14:
        for p2 in primes:
            if cnt[p2] >= 4 and p1 != p2:
                res += 1

for p1 in primes:
    if cnt[p1] >= 24:
        for p2 in primes:
            if cnt[p2] >= 2 and p1 != p2:
                res += 1

for p1 in primes:
    if cnt[p1] >= 74:
        res += 1

print(res)

Submission status: Accepted

Solution code:
N = int(input())

# 1 75, 3 25, 5 15 

def find_primes(n):
    nums=list(range(2,n+1))
    primes = []
    while nums:
        p = nums[0]
        primes.append(p)
        for _ in range(6):
            nums = [n if n%p else n//p for n in nums]
        nums = [n for n in nums if n!=1]
    return primes
assert(find_primes(30)[9]==29)

#primes = find_primes(100)

def primes_of_factor(n):
    nums=list(range(1,n+1))
    primes = find_primes(n)
    ret = {p:0 for p in primes}
    for p in primes:
        s = sum([n%p==0 for n in nums])
        ret[p] += s
        while s:
            nums = [n//p if n%p==0 else n for n in nums]
            s = sum([n%p==0 for n in nums])
            ret[p] += s
    return ret
assert(primes_of_factor(25)[5]==6)

primes = primes_of_factor(N)

answer = len([v for v in primes.values() if v>=74])

from itertools import permutations

for P,Q in permutations(primes.items(), 2):
    if P[1]>=24 and Q[1]>=2:
        answer +=1
    if P[1]>=14 and Q[1]>=4:
        answer +=1

for P,Q,R in permutations(primes.items(), 3):
    if P[1]>=2 and Q[1]>=4 and R[1]>=4:
        if Q[0]>R[0]:
            answer +=1

print(answer)

Submission status: Accepted

Solution code:
def main():
	n = int(input())
	exp_num = [0]*(n+1)

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

	def num(m:int) -> int:
		return len(list(filter(lambda x: x > m-2, exp_num)))

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

	print(total)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
e = [0] * (N+1)
for i in range(2, N+1):
    cur = i
    for j in range(2, i+1):
        while cur % j == 0:
            e[j] += 1
            cur //= j
def num(m): # e の要素のうち m-1 以上のものの個数
    return len(list(filter(lambda x: x >= m-1, e)))
print(num(75) + num(25) * (num(3) - 1) + num(15) * (num(5) - 1)
    + num(5) * (num(5) - 1) * (num(3) - 2) // 2)

Submission status: Accepted

Solution code:
from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
import collections
from operator import itemgetter
#以下てんぷら
def j(q):
    if q==1: print("Yay!")
    else:print(":(")
    exit(0)


def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
n = ip()                                     #入力整数1つ
#n,q= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
#b = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(5)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#こっから本文
u = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,51,53,59,61,67,71,73,79,83,89,97]

factor = [0 for i in range(100)]
for i in range(2,n+1):
    sn = i
    p = 1
    while p<100:
        p+=1
        if p==100:break
        if sn%p == 0:
            factor[p]+=1
            sn//=p
            p=1
use = [factor[i] for i in range(100) if i in u and factor[i]]
#print([i for i in range(100)])
#print(factor)
#print(use)
ov74 = 0
ov4 = 0
ov14 = 0
ov24 = 0
ov2 = 0
ov4u13 = 0
ov2u3 = 0
ov2u23 = 0
for i in range(len(use)):
    if use[i] >=74:ov74+=1
    if use[i] >= 4:ov4+=1
    if use[i] >=14:ov14+=1
    if use[i] >=24:ov24+=1
    if use[i] == 2 or use[i]==3:ov2u3+=1
    if 14>use[i] and use[i]>=4: ov4u13+=1
    if 24>use[i] and use[i]>=2: ov2u23+=1
q = ov74
w = combinations(ov4,2) * ov2u3 + 3*combinations(ov4,3)
e = ov14 * ov4u13 + permutations(ov14,2)
r = ov24 * ov2u23 + permutations(ov24,2)
print(q+w+e+r)

Submission status: Accepted

Solution code:
from math import*
from collections import*
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b += 1
    if n > 1:
        fct.append(n)
    return fct

def fil(num):
    return len([1 for k,v in l.items() if v>=num-1])

l=[]
for i in range(2,int(input())+1):
    l.extend(factorize(i))
    
l=Counter(l)
#print(l)

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

Submission status: Accepted

Solution code:
import bisect


def soin(n):
    re = []
    while n > 1:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                re += [i]
                n //= i
                break
        else:
            re += [n]
            n = 0
    return re


n = int(input())
sol = []
for i in range(2, n + 1):
    sol += soin(i)

sisu = []
for sk in set(sol):
    sisu += [sol.count(sk)]

sisu.sort()
lsi = len(sisu)
c74 = lsi - bisect.bisect_left(sisu, 74)
c24 = lsi - bisect.bisect_left(sisu, 24)
c14 = lsi - bisect.bisect_left(sisu, 14)
c4 = lsi - bisect.bisect_left(sisu, 4)
c2 = lsi - bisect.bisect_left(sisu, 2)

c24_2 = c24 * (c2 - 1)
c14_4 = c14 * (c4 - 1)
c4_4_2 = c4 * (c4 - 1) * (c2 - 2) // 2

print(c74 + c24_2 + c14_4 + c4_4_2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def POW(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x
    elif y % 2 == 0:
        return POW(x, y // 2) ** 2 % MOD
    else:
        return POW(x, y // 2) ** 2 * x % MOD
def mod_factorial(x, y): return x * POW(y, MOD - 2) % MOD
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 input()
from collections import Counter

def main():
    N = II()
    factors = Counter()
    for k in range(1, N + 1):
        for i in (2,3,5,7):
            while k % i == 0:
                factors[i] += 1
                k //= i
        if k != 1:
            factors[k] += 1
    # 75 = 3 * 5 * 5
    nfactors = sorted(factors.values())
    ans = 0
    dp = [0] * 76
    dp[1] = 1
    for cnt in nfactors:
        pre = dp
        dp = [0] * 76
        for c in range(1, cnt + 2):
            for k in range(75 // c + 1):
                dp[k * c] += pre[k]
    ans = dp[75]
    return ans

print(main())

Submission status: Accepted

Solution code:
def get_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]]

def get_division(N, prime):
    counter = 0
    _prime = prime
    while _prime < N:
        counter += N // _prime
        _prime *= prime
    return counter

N = int(input())

primes = get_primes(N)

counter = 0
counter1 = 0
counter2 = 0
counter3 = 0
counter4 = 0
for prime in primes:
    if get_division(N, prime) >= 74:
        counter += 1
    if get_division(N, prime) >= 24:
        counter1 += 1
    if get_division(N, prime) >= 14:
        counter2 += 1
    if get_division(N, prime) >= 4:
        counter3 += 1
    if get_division(N, prime) >= 2:
        counter4 += 1

total = counter + (counter4 - 1) * counter1 + (counter3 - 1) * counter2 + \
        (counter4 - 2) * counter3 * (counter3 - 1) / 2
print(int(total))

Submission status: Accepted

Solution code:
n = int(input())
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
ps = {}
def primes(x, k):
    cnt = 0
    for i in range(1,x+1):
        while i % k == 0:
            cnt += 1
            i = i / k
    return cnt
for i in prime:
    ps[i] = primes(n, i)
sevfo = 0
twefo = 0
fot = 0
four = 0
two = 0
for value in ps.values():
    if value >= 74:
        sevfo += 1
        twefo +=1
        fot += 1
        four += 1
        two += 1
    elif value >= 24:
        twefo += 1
        fot += 1
        four += 1
        two += 1
    elif value >= 14:
        fot += 1
        four += 1
        two += 1
    elif value >= 4:
        four += 1
        two += 1
    elif value >= 2:
        two += 1
if (four >= 2 and two >= 3) or sevfo >= 1 or (twefo >= 1 and two >= 2) or (fot >= 1 and four >= 2):
    a = int(((four-1)*four / 2)*(two-2))
    b = fot * (four -1)
    c = twefo * (two-1)
    d = sevfo
    print(a+b+c+d)
else:
    print(0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int):
    def is_prime(n):
        i = 2
        while i * i <= n:
            if n % i == 0:
                return False
            i += 1
        return True
    def comb(n, k):
        if n < k:
            return 0
        ret = 1
        for i in range(k):
            ret *= n - i
            ret //= (i + 1)
        return ret
    primes = []
    for i in range(2, N + 1):
        if is_prime(i):
            primes.append(i)

    count = [0] * (N + 1)
    def count_up(n):
        for p in primes:
            while n >= p and n % p == 0:
                count[p] += 1
                n //= p
        return
    for i in range(2, N + 1):
        count_up(i)
    count.sort(reverse=True)
    over_75 = 0
    over_25 = 0
    over_15 = 0
    over_5 = 0
    over_3 = 0
    for c in count:
        if c >= 2:
            over_3 += 1
        if c >= 4:
            over_5 += 1
        if c >= 14:
            over_15 += 1
        if c >= 24:
            over_25 += 1
        if c >= 74:
            over_75 += 1
    ret = (over_75 + over_25 * (over_3 - 1) +
           over_15 * (over_5 - 1) +
           comb(over_5, 2) * (over_3 - 2))
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

a,b,c,d,e=0,0,0,0,0
for i in range(N+1):
    if div[i]>=74:
        a+=1
        b+=1
        c+=1
        d+=1
        e+=1
    elif div[i]>=24:
        a+=1
        b+=1
        c+=1
        d+=1
    elif div[i]>=14: 
        a+=1
        b+=1
        c+=1
    elif div[i]>=4:
        a+=1
        b+=1
    elif div[i]>=2:
        a+=1

if a<3 or b<2: print(0)
else:
    ans=b*(b-1)*(a-2)//2
    ans+=d*(a-1)
    ans+=c*(b-1)
    ans+=e
    print(ans)

Submission status: Accepted

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

n=int(input())
num=math.factorial(n)
factors=prime_factors(num)
es=list(Counter(factors).values())
m=len(es)
ans=0

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

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

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

for i in range(m):
  for j in range(i+1,m):
    for k in range(m):
      if i!=k and j!=k and es[i]>=4 and es[j]>=4 and es[k]>=2:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
p_list = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
dp = np.zeros([N, len(p_list)], dtype=int)
for i in range(2, N+1):
    for j in range(len(p_list)):
        x = p_list[j]
        power = 0
        while i%(x**(power+1)) == 0:
            power += 1
        dp[i-1, j] = dp[i-2, j] + power
factors = dp[-1]
num_g3 = len([1 for x in factors if x >= 2])
num_g5 = len([1 for x in factors if x >= 4])
num_g15 = len([1 for x in factors if x >= 14])
num_g25 = len([1 for x in factors if x >= 24])
num_g75 = len([1 for x in factors if x >= 74])
ans = 0
if num_g3 >= 3 and num_g5 >= 2:
    add = (num_g5*(num_g5-1))//2 * (num_g3-2)
    ans += add
if num_g15 >= 1:
    add = num_g15 * (num_g5-1)
    ans += add
if num_g25 >= 1:
    add = num_g25 * (num_g3-1)
    ans += add
if num_g75 >= 1:
    ans += num_g75
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
def primes(n):
  ass = []
  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
  for i in range(len(is_prime)):
    if is_prime[i]:
      ass.append(i)
  return ass
L = primes(N)
factorial_factor = []
for i in range(len(L)):
  k = L[i]
  cnt = 0
  cur = 1
  while N//k > 0:
    cnt += N//k
    cur += 1
    k = L[i]**(cur)
  factorial_factor.append([L[i],cnt])
ans = 0
A,B,C,D,E,F = 0,0,0,0,0,0
for i in range(len(factorial_factor)):
  if factorial_factor[i][1] >= 74:
    ans += 1
for i in range(len(factorial_factor)):
  if factorial_factor[i][1] >= 14:
    A += 1
  elif factorial_factor[i][1] >= 4:
    B += 1
ans += A*(A-1)+A*B
for i in range(len(factorial_factor)):
  if factorial_factor[i][1] >= 24:
    C += 1
  elif factorial_factor[i][1] >= 2:
    D += 1
ans += C*(C-1)+C*D
for i in range(len(factorial_factor)):
  if factorial_factor[i][1] >= 4:
    E += 1
  elif factorial_factor[i][1] >= 2:
    F += 1
ans += E*(E-1)*F//2+E*(E-1)*(E-2)//2
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def get_soinsu(n):
    if n ==1:
        return
    for p in soinsu.keys():
        if n%p == 0:
            soinsu[p] += 1
            get_soinsu(n//p)
            break
    else:
        soinsu[n] = 1

soinsu = {}
for i in range(2,N+1):
    get_soinsu(i)

tmp3 = soinsu.values()
    
#素因数が(74)個の数の選び方
num_74 = len([tmp for tmp in tmp3 if tmp >= 74])

#素因数が(2,24)個の数の選び方
num_24_2 = len([tmp for tmp in tmp3 if tmp >= 24]) * (len([tmp for tmp in tmp3 if tmp >= 2])-1)

#素因数が(4,14)個の数の選び方
num_14_4 = len([tmp for tmp in tmp3 if tmp >= 14]) * (len([tmp for tmp in tmp3 if tmp >= 4])-1)

#素因数が(2,4,4)個の数の選び方
tmp2 = len([tmp for tmp in tmp3 if tmp >= 4])
num_4_4_2 = max(0,tmp2*(tmp2-1)*(len([tmp for tmp in tmp3 if tmp >= 2])-2)//2)

print(num_74 + num_24_2 + num_14_4 + num_4_4_2)

Submission status: Accepted

Solution code:
n=int(input())
N=1
for i in range(n):
    N*=(i+1)
a=[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]
l=[0 for i in range(len(a))]
k=0
for i in a:
    tmp=N
    while True:
        if tmp%i==0:
            l[k]+=1
            tmp=tmp//i
        else:
            k+=1
            break
up74=len([i for i in l if i>=74])
up24=len([i for i in l if i>=24])
up14=len([i for i in l if i>=14])
up4=len([i for i in l if i>=4])
up2=len([i for i in l if i>=2])
print(up74+up24*(up2-1)+up14*(up4-1)+up4*(up4-1)//2*(up2-2))

Submission status: Accepted

Solution code:
n = int(input())
import math
ans1 = 0
ans2 = 0
fn = math.factorial(n)
prime = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

for p in prime:
    if fn%(p**74) == 0:
        ans1 += 1
    for q in prime:
            if p != q:
                if fn%((p**14)*(q**4)) == 0:
                    ans1 += 1
                if fn%((p**24)*(q**2)) == 0:
                    ans1 += 1
                for r in prime:
                    if p != r and q != r:
                        if fn%((p**4)*(q**4)*(r**2)) == 0:
                            ans2 += 1
print(ans1+int(ans2/2))

Submission status: Accepted

Solution code:

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

primes = []
for i in range(2,50): # prime > 50 never appear twice
    if is_prime(i):
        primes.append(i)

def make_zeroed():
    return [0] * len(primes)

factorized = []
factorized.append(make_zeroed())
for i in range(2, 101):
    lst = make_zeroed()
    for k, p in enumerate(primes):
        if i < p:
            break
        while i % p == 0:
            lst[k] += 1
            i = i // p
    factorized.append(lst)

sum_factorized = []
for i in range(1,101):
    lst = make_zeroed()
    for j in range(0, i):
        for k, f in enumerate(factorized[j]):
            lst[k] += f
    sum_factorized.append(lst)

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

def nCr(n,r):
    if r > n:
        return 0
    return fact(n) // fact(r) // fact(n - r)

def getelems(n):
    lst = sum_factorized[n-1]
    elems = {}
    elems[3] = len([x for x in lst if x >= 2])
    elems[5] = len([x for x in lst if x >= 4])
    elems[15] = len([x for x in lst if x >= 14])
    elems[25] = len([x for x in lst if x >= 24])
    elems[75] = len([x for x in lst if x >= 74])
    return elems

def solve(n):
    elems = getelems(n)
    ans = 0
    # 3 * 5 * 5
    ans += nCr(elems[5], 2) * nCr(elems[3] - 2, 1)
    # 5 * 15
    ans += nCr(elems[15], 1) * nCr(elems[5] - 1, 1)
    # 3 * 25
    ans += nCr(elems[25], 1) * nCr(elems[3] - 1, 1)
    # 75
    ans += nCr(elems[75], 1)
    return ans

answers = {}
for i in range(1,101):
    answers[i] = solve(i)

print(answers[int(input())])

Submission status: Accepted

Solution code:
n = int(input())

def f_pf(n):
    pf = {}
    for i in range(2, n + 1):
        for j in range(2, i + 1):
            while i % j == 0:
                pf[j] = pf.get(j, 0) + 1
                i //= j
    return pf

def cnt(x):
    cnt = 0
    for v in f_pf(n).values():
        if v >= x - 1:
            cnt += 1
    return cnt
        
ans = cnt(75) + cnt(25) * (cnt(3) - 1) + cnt(15) * (cnt(5) - 1) + cnt(5) * (cnt(5) - 1) * (cnt(3) - 2) // 2

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

def f_pf(n):
    pf = {}
    for i in range(2, n + 1):
        for j in range(2, i + 1):
            while i % j == 0:
                pf[j] = pf.get(j, 0) + 1
                i //= j
    return pf
    
mt75 = 0
mt25 = 0
mt15 = 0
mt5 = 0
mt3 = 0
for v in f_pf(n).values():
    if v >= 74:
        mt75 += 1
    if v >= 24:
        mt25 += 1
    if v >= 14:
        mt15 += 1
    if v >= 4:
        mt5 += 1
    if v >= 2:
        mt3 += 1
        
ans = 0
ans += mt75
ans += max(0, mt25 * (mt3 - 1))
ans += max(0, mt15 * (mt5 - 1))
ans += max(0, mt5 * (mt5 - 1) * (mt3 - 2) // 2)

print(ans)