Problem:


Score : 400 points

Problem Statement

You are given an integer N. Among the divisors of N! (= 1 \times 2 \times ... \times N), how many Shichi-Go numbers (literally "Seven-Five numbers") are there?

Here, a Shichi-Go number is a positive integer that has exactly 75 divisors.

Note

When a positive integer A divides a positive integer B, A is said to a divisor of B.
For example, 6 has four divisors: 1, 2, 3 and 6.

Constraints

1 \leq N \leq 100

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the number of the Shichi-Go numbers that are divisors of N!.

Sample Input 1

9

Sample Output 1

0

There are no Shichi-Go numbers among the divisors of 9! = 1 \times 2 \times ... \times 9 = 362880.

Sample Input 2

10

Sample Output 2

1

There is one Shichi-Go number among the divisors of 10! = 3628800: 32400.

Sample Input 3

100

Sample Output 3

543



Sample input:
9


Sample output:
0

Submission status: Accepted

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

def make_divisors(n):
    divisors_set=set()
    for i in range(1,int(n**0.5)+1):
        if n % i == 0:
            divisors_set.add(i)
            divisors_set.add(n//i)
    divisors_list=list(divisors_set)
    divisors_list.sort()
    return divisors_list

def make_primes(n):
    primes_list=[]
    while n % 2 == 0:
        primes_list.append(2)
        n = n//2
    f = 3
    while f * f <= n:
        if n % f == 0:
            primes_list.append(f)
            n = n//f
        else:
            f += 2
    if n != 1:
        primes_list.append(n)
    return primes_list

def cnt75(d):
    ans = 0
    for key in d.keys():
        if d[key] >= 75-1:
            ans += 1
    return ans

def cnt25_3(d):
    ans25 = 0
    ans3 = 0
    for key in d.keys():
        if d[key] >= 25-1:
            ans25 += 1
        elif d[key] >= 3-1:
            ans3 += 1
    #return ans25*(ans25-1+ans3)-(ans25*(ans25-1) )//2
    return ans25 * (ans25+ans3-1)

def cnt15_5(d):
    ans15 = 0
    ans5 = 0
    for key in d.keys():
        if d[key] >= 15-1:
            ans15 += 1
        elif d[key] >= 5-1:
            ans5 += 1
    #return ans15*(ans15-1+ans5)-(ans15*(ans15-1) )//2
    return ans15*(ans15+ans5-1)


def frac(n):
    if n == 1:
        return 1
    else:
        return n*frac(n-1)

def cnt5_5_3(d):
    ans5 = 0
    ans3 = 0
    for key in d.keys():
        if d[key] >= 5-1:
            ans5 += 1
        elif d[key] >= 3-1:
            ans3 += 1
    #return (ans5*(ans5-1))/2*ans3 + frac(ans5)//frac(2)//frac(ans5-2)
    return ans5*(ans5-1)*(ans5+ans3-2)//2 


#print( len(make_divisors(1*2*3*4*5*6*7*8*9*10) )) 
#cnt=0
#print(make_primes(6))
primes=[]
for i in range(1,N+1):
    #cnt+=len(make_primes(i))
    primes.extend(make_primes(i))
    #print(i,len(make_primes(i)))
    #print(make_primes(i))
#print(cnt)
#print(len(primes))
c=collections.Counter(primes)
#print(c)
print(cnt75(c)+cnt25_3(c)+cnt15_5(c)+cnt5_5_3(c) )
#print(2**8 * 3**4 * 5**2 * 7 )

Submission status: Accepted

Solution code:
def factorize_factorial(n):
    # 階乗の素因数分解
    e = [0] * 101
    for k in range(2, n + 1):
        divisor = 2
        cnt = 0
        while k % divisor == 0:
            k //= divisor
            cnt += 1
        if cnt > 0:
            e[divisor] += cnt

        divisor = 3
        while k > 1:
            cnt = 0
            while k % divisor == 0:
                k //= divisor
                cnt += 1
            if cnt > 0:
                e[divisor] += cnt
            divisor += 2
    return e


def count(k, e):
    # 素因数分解テーブルからべき数k以上の要素数を求める
    return len(tuple(filter(lambda x: x >= k, e)))


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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a=[0]*(n+1)
for i in range(2,n+1):
    x=i
    for j in range(2,n+1):
        while x%j==0:
            a[j]+=1
            x//=j
def num(n):
    return len(list(filter(lambda x: x>=n-1,a)))

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
n=int(input())
sosu=[0]*(n+1)
for i in range(2,n+1):
    tmp=i
    for j in range(2,i+1):
        while tmp%j==0:
            sosu[j]+=1
            tmp//=j

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

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

def p_f(n):
    L = []
    c = 2
    while c <= n:
        if n%c == 0:
            L.append(c)
            n /= c
        else:
            c += 1
    return L


if N == 1:
    print(0)
else:
    dic = {}
    for i in range(2, N+1):
        L = p_f(i)
        for j in range(len(L)):
            if L[j] in dic:
                dic[L[j]] += 1
            else:
                dic[L[j]] = 1
    num3 = 0
    num5 = 0
    num15 = 0
    num25 = 0
    num75 = 0
    for key in dic:
        if dic[key] >= 2:
            num3 += 1
            if dic[key] >= 4:
                num5 += 1
                if dic[key] >= 14:
                    num15 += 1
                    if dic[key] >= 24:
                        num25 += 1
                        if dic[key] >= 74:
                            num75 += 1
    ans = num75 + num25*(num3-1) + num15*(num5-1) + num5*(num5-1)//2*(num3-2)
    print(ans)

Submission status: Accepted

Solution code:
#75=3*5*5 
n=int(input())
a=[0]*100
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct
for i in range(n):
	for j in range(len(factorize(i+1))):
		a[factorize(i+1)[j]]+=1
def comb(a,b):
	p=1
	for i in range(b):
		p*=a-i
	for j in range(b):
		p//=j+1
	return p
cnt_74=cnt_24=cnt_14=cnt_4=cnt_2=0
for i in range(100):
	if a[i]>=74:
		cnt_74+=1
	elif a[i]>=24:
		cnt_24+=1
	elif a[i]>=14:
		cnt_14+=1
	elif a[i]>=4:
		cnt_4+=1
	elif a[i]>=2:
		cnt_2+=1
cnt_24+=cnt_74
cnt_14+=cnt_24
cnt_4+=cnt_14
cnt_2+=cnt_4
ans=0
#3*5*5
ans+=max(comb(cnt_4,2)*(cnt_2-2),0)
#3*25
ans+=(cnt_24)*(cnt_2-1)
#5*15
ans+=(cnt_4-1)*cnt_14
#75
ans+=cnt_74
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def factorization(num):
    import math
    # 因数分解した結果をタプルのリストで返す
    # [(prime, count), ...]
    MAX_PRIME = int(math.sqrt(num)) + 1
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in range(2, MAX_PRIME+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    insu = []
    tmp = num
    max_count = 0
    for i in range(len(primes)):
        count = 0
        while tmp%primes[i] == 0:
            tmp //= primes[i]
            count += 1
        if count > 0:
            insu.append((primes[i], count))
            max_count = max(max_count, count)
        if tmp == 1:
            break
    if tmp != 1:
        insu.append((tmp, 1))
    return insu

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

    dic = {}
    for i in range(1, N+1):
        insu = factorization(i)
        for p, count in insu:
            if p in dic:
                dic[p] += count
            else:
                dic[p] = count
    dic = np.array(sorted(dic.values()))
    
    def cc(num):# num-1以上の要素の個数
        return np.count_nonzero(dic >= num-1)
    
    print(cc(75) + cc(25) * (cc(3) - 1) + cc(15) * (cc(5) - 1) + cc(5) * (cc(5) - 1) * (cc(3) - 2) // 2)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

#エラトステネス
L = [1 for i in range(101)]
L[0] = 0
L[1] = 0
plist = []
for i in range(101):
	if L[i] == 1:
		plist.append(i)
		c = 2
		while True:
			if i * c <= 100:
				L[i * c] = 0
				c += 1
			else:
				break

#初期化
N = int(input())
if N <= 9:
	print(0)
else:
	D = defaultdict(int)
	for i in range(1, N + 1):
		m = i
		while m != 1:
			for j in plist:
				if m % j == 0:
					D[j] += 1
					m = m // j
					break

	data = []
	for i in D:
		data.append(D[i])
	ans = 0
	n = len(data)
	for i in range(n):
		if data[i] >= 74:
			ans += 1
	for i in range(n):
		for j in range(n):
			if i != j:
				if data[i] >= 2 and data[j] >= 24:
					ans += 1
				if data[i] >= 4 and data[j] >= 14:
					ans += 1
	for i in range(n):
		for j in range(n):
			for k in range(j + 1, n):
				if i != j and j != k and k != i:
					if data[i] >= 2 and data[j] >= 4 and data[k] >= 4:
						ans += 1
	print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    a = [7,5,3]
    if n in a:
        print("YES")
    else:
        print("NO")
    return

#B
def B():
    s = S()
    ans = inf
    for i in range(len(s) - 2):
        ans = min(ans, abs(753-int("".join(s[i:i + 3]))))
    print(ans)
    return

#C
def C():
    s = II()
    n = len(str(s))
    ans = 0
    for i in range(3,n+1):
        c = itertools.product(["3", "5", "7"], repeat=i)
        for ci in c:
            if len(set(ci)) < 3:
                continue
            if int("".join(ci)) <= s:
                ans += 1
    print(ans)

        
    return

def primes(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    """ 6以上の数であれば p (素数) <= n のlistを返す """
    n, correction = n - n % 6 + 6, 2 - (n % 6 > 1)
    sieve = [True] * (n // 3)
    for i in range(1, int(n ** 0.5) // 3 + 1):
        if sieve[i]:
            k = 3 * i + 1 | 1
            sieve[k * k                     // 3::2 * k] = [False] * ((n // 6 - k * k                     // 6 - 1) // k + 1)
            sieve[k * (k - 2 * (i & 1) + 4) // 3::2 * k] = [False] * ((n // 6 - k * (k - 2 * (i & 1) + 4) // 6 - 1) // k + 1)
    return [2, 3] + [3 * i + 1 | 1 for i in range(1, n // 3 - correction) if sieve[i]]
#D
def D():
    n = II()
    primelis = primes(100)
    d = {2: 0, 4: 0, 14: 0, 24: 0, 74: 0}
    for i in primelis:
        b = n
        tmp = 0
        while b // i:
            tmp += (b // i)
            b = (b // i)
        for x in d.keys():
            d[x] += (tmp >= x)
    ans = 0
    ans += (d[2] - 1) * d[24]
    ans += (d[4] - 1) * d[14]
    ans += d[74]
    ans += (d[2] - 2) * (d[4] - 1) * d[4] // 2
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def prime(n,is_prime=True):
    """
    n: positive integer
    if is_prime: return n is prime
    else: return list of prime <= n
    """
    if n<=1: return False if is_prime else []
    S=[1]*(n+1)
    S[0]=0; S[1]=0
    for i in range(2,n):
        if S[i]==0: continue
        for j in range(2*i,n+1,i):
            S[j]=0
    if is_prime: return bool(S[n])
    else: return [p for p in range(n+1) if S[p]]
def resolve():
    """
    p^74,p^24q^2,p^14q^4,p^4q^4r^2
    """
    n=int(input())
    P=prime(n,False)
    bin=[0]*48
    for p in P:
        if p>47: continue # p<=47
        q=p
        while(q<=n):
            bin[p]+=n//q
            q*=p
    c2=len([0 for i in bin if i>=2])
    c4=len([0 for i in bin if i>=4])
    c14=len([0 for i in bin if i>=14])
    c24=len([0 for i in bin if i>=24])
    c74=len([0 for i in bin if i>=74])
    ans=0
    ans+=c74
    ans+=c24*(c2-1)
    ans+=c14*(c4-1)
    ans+=c4*(c4-1)//2*(c2-2)
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import collections


def eratosthenes(n):
    sieve = [True for _ in range(n + 1)]
    sieve[0] = False
    sieve[1] = False

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False
    if n > 1:
        _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


n = int(input())
sieve = eratosthenes(n)
primes = [i for i in range(n + 1) if sieve[i]]
counter = collections.Counter()
for i in range(2, n + 1):
    for p in primes:
        while i % p == 0:
            counter[p] += 1
            i //= p
        if i == 1:
            break

counter2 = collections.Counter()
for i in [2, 4, 14, 24, 74]:
    for p in primes:
        if counter[p] >= i:
            counter2[i] += 1

c0 = counter2[74]
c1 = counter2[24] * (counter2[2] - 1)
c2 = counter2[14] * (counter2[4] - 1)
c3 = (counter2[4] * (counter2[4] - 1) * (counter2[2] - 2)) // 2
print(c0 + c1 + c2 + c3)

Submission status: Accepted

Solution code:
N = int(input())

prime = []
prime.append(2)
k = 0
for i in range(3, N+1):
    if prime[k]*prime[k] < i:
         k += 1
    for j in range(0, k+1):
        if i%prime[j] == 0:
            break
    else:
        prime.append(i)

count = []
for p in prime:
    i = 0
    q = p
    while q < N:
        i += N//q
        q *= p
    count.append(i)

ans = 0

for c in count:
    if 74 <= c:
        ans += 1

for i, ci in enumerate(count):
    if ci < 24:
        break
    for j, cj in enumerate(count):
        if cj < 2:
            break
        if i != j:
             ans += 1

for i, ci in enumerate(count):
    if ci < 14:
        break
    for j, cj in enumerate(count):
        if cj < 4:
            break
        if i != j:
             ans += 1

for i, ci in enumerate(count):
    if ci < 4:
        break
    M = len(count)
    for j in range(i+1, M):
        if count[j] < 4:
            break
        for k, ck in enumerate(count):
            if ck < 2:
                break
            if k != i and k != j:
                ans += 1

print(ans)

Submission status: Accepted

Solution code:
# M = a ** x * b ** y * c ** z
# の約数の個数は(x + 1)*(y + 1)*(z + 1)
# なので約数が75個になるには、以下パターンが考えられる
# 75
# 25 * 3
# 15 * 5
# 5 * 5 * 3
# よって1～Nまで素因数分解して、各素因数の指数部分の値を求めて
# 計算する

import itertools

def main():
    N = int(input())
    d = [0] * (N+1)

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

    ans = 0
    for i in d:
        if i >= 74:
            ans += 1
    for (x, y, z) in itertools.combinations(d,3):
        for a, b, c in [[4, 4, 2],[4, 2, 4],[2, 4, 4]]:
            if x >= a and y >= b and z >= c:
                ans += 1

    for (x, y) in itertools.combinations(d,2):
        for a, b in [[24,2],[14,4],[4,14],[2,24]]:
            if x >= a and y >= b:
                ans += 1

    print(ans)


    

main()

Submission status: Accepted

Solution code:
from math import factorial
from itertools import combinations
N = int(input())
LIM = factorial(N)
pls = [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]
ans = 0
for x, y, z in combinations(pls, 3):
  if LIM%((x**4)*(y**4)*(z**2))==0:
    ans += 1
  if LIM%((y**4)*(z**4)*(x**2))==0:
    ans += 1
  if LIM%((z**4)*(x**4)*(y**2))==0:
    ans += 1
for x, y in combinations(pls,2):
  if LIM%((x**14)*(y**4))==0:
    ans += 1
  if LIM%((y**14)*(x**4))==0:
    ans += 1
  if LIM%((x**24)*(y**2))==0:
    ans += 1
  if LIM%((y**24)*(x**2))==0:
    ans += 1
for x in pls:
  if LIM%(x**74)==0:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
P = [1 for _ in range(100)]
P[0]=0
P[1]=0
for i in range(2,11):
    for j in range(i*i,100,i):
        P[j]=0
Q = []
for i in range(100):
    if P[i]==1:
        Q.append(i)
N = int(input())
G = {p:0 for p in Q}
for n in range(2,N+1):
    k = n
    i = 0
    while k>1 and i<len(Q):
        if k%Q[i]==0:
            k = k//Q[i]
            G[Q[i]] += 1
        else:
            i += 1
C2 = 0
C4 = 0
C14 = 0
C24 = 0
C74 = 0
for x in G:
    if G[x]>=2:
        C2 += 1
    if G[x]>=4:
        C4 += 1
    if G[x]>=14:
        C14 += 1
    if G[x]>=24:
        C24 += 1
    if G[x]>=74:
        C74 += 1
cnt = 0
cnt += C24*(C2-1)
cnt += C14*(C4-1)
cnt += (C4*(C4-1))//2*(C2-2)
cnt += C74
print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())

def 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 factor_factorize(n, d):
    if n == 1:
        return d
    d.extend(factorize(n))
    return factor_factorize(n-1, d)

F = Counter(factor_factorize(N, []))

# (4, 4, 2), (14, 4), (24, 2), (74,)
cases = []

n1 = [True for v in F.values() if v >= 4].count(True)
m1 = [True for v in F.values() if 4 > v >= 2].count(True)
cases.append(n1 * (n1-1) // 2 * max(0, m1+n1-2))

n2 = [True for v in F.values() if v >= 14].count(True)
m2 = [True for v in F.values() if 14 > v >= 4].count(True)
cases.append(n2 * max(0, m2+n2-1))

n3 = [True for v in F.values() if v >= 24].count(True)
m3 = [True for v in F.values() if 24 > v >= 2].count(True)
cases.append(n3 * max(0, m3+n3-1))

n4 = [True for v in F.values() if v >= 74].count(True)
cases.append(n4)

print(sum(cases))

Submission status: Accepted

Solution code:
#15:30
'''
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
 0 1 2 3  4  5  6  7  8  9 10 11 12 13 14
'''
n = int(input())
prime = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
fact = [0,0,0,0,0]
check = []
for i in range(15):
  p = prime[i]
  d = n
  tmp = 0
  while d != 0:
    d //= p
    tmp += d
  check.append(tmp)
  if tmp >= 74:
    fact[0] += 1
  if tmp >= 24:
    fact[1] += 1
  if tmp >= 14:
    fact[2] += 1
  if tmp >= 4:
    fact[3] += 1
  if tmp >= 2:
    fact[4] += 1
#print(check)
#print(fact)
ans = 0
ans += fact[0]
ans += fact[1] * (fact[4]-1)
ans += fact[2] * (fact[3]-1)
ans += fact[3] * (fact[3]-1) * (fact[4]-2) // 2
print(ans)

Submission status: Accepted

Solution code:
#D問題
import math
N = int(input())

prime = []
for i in range(2,N+1):
    n = math.ceil(math.log2(i))
    flag = 0
    for j in range(2,n+1):
        if i%j == 0:
            flag = 1
            break
    if flag == 0:
        if i != 49:
            prime.append(i)

count = 0
plen = len(prime)
#(74)
for i in range(plen):
    p = prime[i]
    pc = 0
    while p <= N:
        pc+=(N//p)
        p*=prime[i]
    if pc >= 74:
        count+=1
        #print(prime[i])
#(2,24)
for i in range(plen):
    for j in range(plen):
        if i == j:
            continue
        p1 = prime[i]
        p2 = prime[j]
        pc1 = 0
        while p1 <= N:
            pc1+=(N//p1)
            p1*=prime[i]
        pc2 = 0
        while p2 <= N:
            pc2+=(N//p2)
            p2*=prime[j]
        if pc1 >= 2 and pc2 >= 24:
            count+=1
            #print(prime[i],prime[j])
#(4,14)
for i in range(plen):
    for j in range(plen):
        if i == j:
            continue
        p1 = prime[i]
        p2 = prime[j]
        pc1 = 0
        while p1 <= N:
            pc1+=(N//p1)
            p1*=prime[i]
        pc2 = 0
        while p2 <= N:
            pc2+=(N//p2)
            p2*=prime[j]
        if pc1 >= 4 and pc2 >= 14:
            count+=1
            #print(prime[i],prime[j])
#(2,4,4)
for i in range(plen):
    for j in range(plen):
        if i == j:
            continue
        for k in range(plen):
            if i == k or j == k or j < k:
                continue
            p1 = prime[i]
            p2 = prime[j]
            p3 = prime[k]
            pc1 = 0
            while p1 <= N:
                pc1+=(N//p1)
                p1*=prime[i]
            pc2 = 0
            while p2 <= N:
                pc2+=(N//p2)
                p2*=prime[j]
            pc3 = 0
            while p3 <= N:
                pc3+=(N//p3)
                p3*=prime[k]
            if pc1 >= 2 and pc2 >= 4 and pc3 >= 4:
                count+=1
                #print(prime[i],prime[j],prime[k])

print(count)
#print(prime)

Submission status: Accepted

Solution code:
import itertools
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 = cur//j

ans = 0
for x in e :
  if x>=74:
    ans +=1
for i in range(N+1):
  for j in range(i+1,N+1):
    for k in range(j+1,N+1):
        for a, b, c in [[4, 4, 2], [4, 2, 4], [2, 4, 4]]:
          if e[i] >= a and e[j] >= b and e[k] >= c:
            ans += 1
for (x, y) in itertools.combinations(e, 2):
  #print(x, y)
  for a, b in [(24, 2), (14, 4), (4, 14), (2, 24)]:
    if x >= a and y >= b:
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
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 = cur//j

ans = 0
for x in e :
  if x>=74:
    ans +=1
for (x, y) in itertools.combinations(e, 2):
  for a, b in [(24, 2), (14, 4), (4, 14), (2, 24)]:
    if x >= a and y >= b:
      ans += 1
for (x, y, z) in itertools.combinations(e, 3):
  for a, b, c in [[4, 4, 2], [4, 2, 4], [2, 4, 4]]:
    if x >= a and y >= b and z >= c:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



q = I()


def sieve(r):
    not_prime = [0] * r
    not_prime[0] = 1
    not_prime[1] = 1
    for i in range(2, r):
        if not_prime[i] == 0:
            for j in range(i*2, r, i):
                not_prime[j] = 1
    return [k for k in range(r) if not not_prime[k]]



primes = sieve(100)
n = len(primes)
multiple_cnt = [0] * n
for m in range(len(primes)):
    ret = q
    p = primes[m]
    while ret:
        ret //= p
        multiple_cnt[m] += ret


multiple_cnt.sort()
ans = 0
ans += (n - bisect_left(multiple_cnt, 74))
ans += (n - bisect_left(multiple_cnt, 24)) * (n - bisect_left(multiple_cnt, 2) - 1)
ans += (n - bisect_left(multiple_cnt, 14)) * (n - bisect_left(multiple_cnt, 4) - 1)
ans += (n - bisect_left(multiple_cnt, 4)) * (n - bisect_left(multiple_cnt, 4) - 1) // 2 * (n - bisect_left(multiple_cnt, 2) - 2)


print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from collections import Counter

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

N = I()
d = defaultdict(int)

for i in range(2,N+1):
    c = Counter(prime_factorize(i))
    for k in c.keys():
        d[k] += c[k]

n2 = 0
n4 = 0
n14 = 0
n24 = 0
n74 = 0
for k in d.keys():
    if d[k]>=74:
        n74 += 1
    if d[k]>=24:
        n24 += 1
    if d[k]>=14:
        n14 += 1
    if d[k]>=4:
        n4 += 1
    if d[k]>=2:
        n2 += 1

ans = 0
if n4>=2 and n2>=3:
    ans += n4*(n4-1)//2 * (n2-2)
if n14>=1 and n4>=2:
    ans += n14*(n4-1)
if n24>=1 and n2>=2:
    ans += n24*(n2-1)
ans += n74

print(ans)

Submission status: Accepted

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


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

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

Submission status: Accepted

Solution code:
N = int(input())

# 素数^a, 素数^b, 素数^c
# print((a+1)*(b+1)*(c+1) = 約数の数)

# p = [2]
# for i in range(3, 101):
#     if any(i % p_i == 0 for p_i in p):
#         continue
#     p.append(i)
p = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
     43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
# print(p)

l = [0]*101
for i in range(2, N+1):
    for p_i in p:
        while i % p_i == 0:
            i //= p_i
            l[p_i] += 1
# print(l[:N+1])

# (3, 5, 5), (15, 5), (3, 25), (75)


def e(m):
    return sum(l_i >= m-1 for l_i in l)

# WHYYYYYYYYYYYY.
print(e(75) + e(25) * (e(3) - 1) + e(15) * (e(5) - 1) +
      e(5) * (e(5) - 1) * (e(3) - 2) // 2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import math

N=int(input())

sosu = []
sosu.append(2)
for i in range(3,N+1):
    Flag = True
    for j in range(len(sosu)):
        if i%sosu[j]==0:
            Flag=False
            break
    if Flag:
        sosu.append(i)

def f(x,k):
    r=0
    while True:
        if x%k==0:
            x//=k
            r+=1
        else:
            break
    return r

yakusu = [1]*len(sosu)
for i in range(1,N+1):
    for j in range(len(sosu)):
        yakusu[j]+=f(i,sosu[j])

count75=0
count25=0
count15=0
count5=0
count3=0
for i in yakusu:
    if i >= 75:
        count75+=1
    if i >= 25:
        count25+=1
    if i >= 15:
        count15+=1
    if i >= 5:
        count5+=1
    if i >= 3:
        count3+=1
ans=0

ans+= count5*(count5-1)//2*(count5-2)
ans+= count5*(count5-1)//2*(count3-count5)
ans+=count15*(count15-1)+count15*(count5-count15)
ans+=count25*(count25-1)+count25*(count3-count25)
ans+=count75
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
M = {}
for n in range(1, N+1):
  f = 2
  while n > 1:
    if n%f == 0:
      if not(f in M): M[f] = 0
      M[f] += 1
      n = n//f
    else:
      f += 1
#print(M)
fs2 = list(filter(lambda f: M[f] >= 2, M))
fs4 = list(filter(lambda f: M[f] >= 4, M))
fs14 = list(filter(lambda f: M[f] >= 14, M))
fs24 = list(filter(lambda f: M[f] >= 24, M))
fs74 = list(filter(lambda f: M[f] >= 74, M))
#print(fs2, fs4, fs14, fs24, fs74)
ps = set()
for f in fs74:
  ps.add(f**74)
for f1 in fs24:
  for f2 in fs2:
    if len({ f1, f2 }) == 2:
      ps.add(f1**24*f2**3)
for f1 in fs14:
  for f2 in fs4:
    if len({ f1, f2 }) == 2:
      ps.add(f1**14*f2**4)
for f1 in fs4:
  for f2 in fs4:
    for f3 in fs2:
      if len({ f1, f2, f3 }) == 3:
        ps.add(f1**4*f2**4*f3**2)
#print(ps)
r = len(ps)
print(r)

Submission status: Accepted

Solution code:
def find_prime_factor(num):
    if num & 1 == 0:
        return 2
    for i in range(3, int(num ** (1 / 2)) + 1):
        if num % i == 0:
            return i
    return num


def prime_factorization(num):
    subtract = num
    result = []
    while subtract > 1:
        factor = find_prime_factor(subtract)
        result.append(factor)
        subtract //= factor
    return result


n = int(input())

# prime and prime's power.
power = {}
for i in range(1, n + 1):
    for prime in prime_factorization(i):
        if prime in power:
            power[prime] += 1
        else:
            power[prime] = 1

count75 = sum(1 for count in power.values() if count >= 74)
count25 = sum(1 for count in power.values() if count >= 24)
count15 = sum(1 for count in power.values() if count >= 14)
count5 = sum(1 for count in power.values() if count >= 4)
count3 = sum(1 for count in power.values() if count >= 2)

ans = count75 \
      + count25 * (count3 - 1) \
      + count15 * (count5 - 1) \
      + (count5 * (count5 - 1) * (count3 - 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 math
dic = {}
N = int(input())
for i in range(2, N+1):
    fact = []
    while i % 2 == 0:
        fact.append(2)
        i //= 2
    f = 3
    while f*f <= i:
        if i%f == 0:
            fact.append(f)
            i //= f
        else:
            f += 2
    if i != 1:
        fact.append(i)
    for j in fact:
        if j in dic:
            dic[j] += 1
        else:
            dic[j] = 1
cnt = 0
s1 = len([k for k, v in dic.items() if v >= 2])
s2 = len([k for k, v in dic.items() if v >= 4])
s3 = len([k for k, v in dic.items() if v >= 14])
s4 = len([k for k, v in dic.items() if v >= 24])
s5 = len([k for k, v in dic.items() if v >= 74])

#3*5*5
if s2 >= 2 and s1 >= 3:
    cnt += s2*(s2-1)/2*(s1-2)
#15*5
if s3 >= 1:
    cnt += s3*(s2-1)
#25*3
if s4 >= 1:
    cnt += s4*(s1-1)
#75
if s5 >= 1:
    cnt += s5
print(int(cnt))