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:
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]
d = [0]*25
n = int(input())
if n < 10:
    print(0)
    exit()
for i in range(2,n+1):
    x = i
    for j in range(25):
        while x%p[j]==0:
            d[j] += 1
            x //= p[j]
d.sort(reverse=True)
four = 0
for i in range(25):
    if d[i] >= 4:
        four += 1
two = 0
for i in range(25):
    if d[i] >= 2:
        two += 1
tw_four = 0
for i in range(25):
    if d[i] >= 24:
        tw_four += 1
one_four = 0
for i in range(25):
    if d[i] >= 14:
        one_four += 1
seven_four = 0
for i in range(25):
    if d[i] >= 74:
        seven_four += 1
if (four < 2 or two < 3):
    print(0)
    exit()
ans = (four*(four-1)//2)*(two-2)
if one_four > 0:
    ans += one_four*(four-1)
if tw_four > 0:
    ans += tw_four*(two-1)
if seven_four > 0:
    ans += seven_four
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
c=0
r=0
for i in range(1,8):
    r+=n//(2**i)
if r>=74:
    c+=1
d=2
q=0
p=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
e=0
f=0
a=0
h=0
for j in range(15):
    q=0
    for i in range(1,7):
        q+=n//(p[j]**i)
    if q>=24:
        e+=1
        f+=1
        a+=1
        h+=1
    elif q>=14:
        f+=1
        a+=1
        h+=1
    elif q>=4:
        h+=1
        a+=1
    elif q>=2:
        h+=1
c+=e*(h-1)+f*(a-1)+(a*(a-1)//2)*(h-2)
print(c)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict

N=input()

C=defaultdict(lambda: 0)

#L=(2,3,5,7)
L=range(2,101)


for i in range(N,0,-1):
	for l in L:
		while i%l==0:
			i/=l
			C[l]+=1

D=defaultdict(lambda: 0)

for x,y in C.items():
	if y>=4:	D[4]+=1
	if y>=2:	D[2]+=1
	if y>=24:D[24]+=1
	if y>=14:D[14]+=1
	if y>=74:D[74]+=1

ans=0

ans+=D[4]*(D[4]-1)/2*(D[2]-2)
ans+=D[24]*(D[2]-1)
ans+=D[14]*(D[4]-1)
ans+=D[74]
print ans

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


def prime_factorize(num):
    """
    This function performs prime factorization on the input natural number.
    The result is returned in the form of a dictionary with the prime number as the key
    and its number as the value.
    :param num:
    :return prime_factor: Dictionary with the prime number as the key and its number as the value.
    """
    prime_factor = {}
    i = 2
    while i ** 2 <= num:
        while num % i == 0:
            num //= i
            if i in prime_factor.keys():
                prime_factor[i] += 1
            else:
                prime_factor[i] = 1
        i += 1
    if num > 1:
        prime_factor[num] = 1
    return prime_factor


import math

fac = math.factorial(N)
prime_fac = prime_factorize(fac)

count = 0
upper_two = {}
upper_four = {}
upper_15 = {}
upper_24 = {}
upper_74 = {}


for k, v in prime_fac.items():
    if v >= 2:
        upper_two[k] = v
    if v >= 4:
        upper_four[k] = v
    if v >= 14:
        upper_15[k] = v
    if v >= 24:
        upper_24[k] = v
    if v >= 74:
        upper_74[k] = v


upper_two = len(upper_two)
upper_four = len(upper_four)
upper_15 = len(upper_15)
upper_24 = len(upper_24)
upper_74 = len(upper_74)


ans = upper_four*(upper_four - 1) * (upper_two-2)//2 \
     + upper_74 + upper_24 * (upper_two-1) + upper_15 * (upper_four-1)


print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

def prime_factor(n):
    res = Counter()
    for i in range(2, int(n**.5) + 1):
        while n % i == 0:
            res[i] += 1
            n //= i
    if n != 1:
        res[n] += 1
    return res

N = int(input())

C = Counter()
for x in range(1, N + 1):
    C += prime_factor(x)

res = [C[k] for k in sorted(C)]
cnt = 0

# 5 * 5 * 3
for i in range(len(res)):
    if res[i] < 2:
        continue
    for j in range(len(res)):
        if j == i or res[j] < 4:
            continue
        for k in range(j + 1, len(res)):
            if k == i or res[k] < 4:
                continue
            cnt += 1
# 25 * 3
for i in range(len(res)):
    if res[i] < 24:
        continue
    for j in range(len(res)):
        if i == j or res[j] < 2:
            continue
        cnt += 1
# 15 * 5
for i in range(len(res)):
    if res[i] < 14:
        continue
    for j in range(len(res)):
        if i == j or res[j] < 4:
            continue
        cnt += 1
# 75
for i in range(len(res)):
    if res[i] < 74:
        continue
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import collections


N = int(input())
if N <=9:
    print(0)
    exit()

np = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53]
a = []
for i in range(2,N+1):
    for num in np:
        l = i
        if i % num ==0:
            q=0
            while(l%num ==0):
                l = l//num
                a.append(str(num))
count_a = collections.Counter(a)
sorted_c = count_a.most_common()
count_75 = 0
count_25 = 0
count_15 = 0
count_5 = 0
count_3 = 0
#print(sorted_c)
for i in range(len(sorted_c)):
    if sorted_c[i][1] >=74:
        count_75 +=1
    if sorted_c[i][1] >=24:
        count_25 +=1
    if sorted_c[i][1] >=14:
        count_15 +=1
    if sorted_c[i][1] >=4:
        count_5+=1
    if sorted_c[i][1] >=2:
        count_3+=1
#print(count_25)
ans = (count_75+ count_25*(count_3-1) + count_15*(count_5-1) 
      + count_5*(count_5-1)*(count_3-2)//2)
print(ans)

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 = 0
count25 = 0
count15 = 0
count5 = 0
count3 = 0
for count in power.values():
    if count >= 74:
        count75 += 1
    elif count >= 24:
        count25 += 1
    elif count >= 14:
        count15 += 1
    elif count >= 4:
        count5 += 1
    elif count >= 2:
        count3 += 1

sum25 = count75 + count25
sum15 = count75 + count25 + count15
sum5 = count75 + count25 + count15 + count5
sum3 = count75 + count25 + count15 + count5 + count3
ans = count75 + sum25 * (sum3 - 1) + sum15 * (sum5 - 1) + (sum5 * (sum5 - 1) * (sum3 - 2)) // 2

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
dict = defaultdict(int)
for i in range(2, N+1):
    for j in range(2, i+1):
        while i > 1:
            if i % j == 0:
                i = i // j
                dict[j] += 1
            else:
                break
count74 = 0
count24 = 0
count14 = 0
count4 = 0
count2 = 0
for k, v in dict.items():
    if v >= 74:
        count74 += 1
        count24 += 1
        count14 += 1
        count4 += 1
        count2 += 1
    elif v >= 24:
        count24 += 1
        count14 += 1
        count4 += 1
        count2 += 1
    elif v >= 14:
        count14 += 1
        count4 += 1
        count2 += 1
    elif v >= 4:
        # print('4',k)
        count4 += 1
        count2 += 1
    elif v >= 2:
        # print('2', k)
        count2 += 1
ans74 = count74
ans242 = count24 * (count2-1)
ans144 = count14 * (count4-1)
ans442 = count4 * (count4-1) // 2 * (count2-2)
print(ans74+ans144+ans242+ans442)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
N = int(input())
# 以下の形の数が75個の約数を持つ
# 素数^4 * 素数^4 * 素数^2
# 素数^14 * 素数^4
# 素数^24 * 素数^2
# 素数^74
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
ct = dd(int)
for i in range(1, N+1):
  for j in primes:
    x = i
    while x % j == 0:
      ct[j] += 1
      x //= j

over74 = []
over24 = []
over14 = []
over4 = []
over2 = []
for k, v in ct.items():
  if v >= 74:
    over74.append(k)
  elif v >= 24:
    over24.append(k)
  elif v >= 14:
    over14.append(k)
  elif v >= 4:
    over4.append(k)
  elif v >= 2:
    over2.append(k)

l2 = len(over2)
l4 = len(over4)
l14 = len(over14)
l24 = len(over24)
l74 = len(over74)
print(
  l2 * (l4+l14+l24+l74) * ((l4+l14+l24+l74) - 1) // 2 +
  (l4+l14+l24+l74) * ((l4+l14+l24+l74) - 1) * ((l4+l14+l24+l74) - 2) // 2 +
  l4 * (l14+l24+l74) +
  (l14+l24+l74) * ((l14+l24+l74) - 1) +
  (l2+l4+l14) * (l24+l74) +
  (l24+l74) * ((l24+l74) - 1) +
  l74
)

Submission status: Accepted

Solution code:
N = int(input())
lim = 1
for i in range(N): lim *= (i+1)
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]

Ans = 0
for i in range(23):
    for j in range(i+1, 24):
        for k in range(j+1, 25):
            a, b, c = Prime[i], Prime[j], Prime[k]
            d, e, f = (a**4)*(b**4)*(c**2), (a**4)*(b**2)*(c**4), (a**2)*(b**4)*(c**4)
            if d <= lim and lim%d == 0: Ans += 1
            if e <= lim and lim%e == 0: Ans += 1
            if f <= lim and lim%f == 0: Ans += 1
for i in range(24):
    for j in range(i+1, 25):
        a, b = Prime[i], Prime[j]
        d, e, f, g = (a**24)*(b**2), (a**2)*(b**24), (a**4)*(b**14), (a**14)*(b**4)
        if d <= lim and lim%d == 0: Ans += 1
        if e <= lim and lim%e == 0: Ans += 1
        if f <= lim and lim%f == 0: Ans += 1
        if g <= lim and lim%g == 0: Ans += 1
for i in range(5):
    if Prime[i] ** 74 <= lim and lim % (Prime[i]**74) == 0: Ans += 1
print(Ans)

Submission status: Accepted

Solution code:
N = int(input())
from math import ceil, sqrt, factorial
from itertools import permutations
def eratosthenes(n):
    l = [1 for i in range(n+1)]
    l[0] = l[1] = 0
    for i in range(2, ceil(sqrt(n))):
        if l[i] == 0: continue
        for j in range(i*2, n+1, i):
            l[j] = 0
    return l

m = factorial(N)
ans = set()

p = eratosthenes(530)

p = [i for i,v in enumerate(p) if v ]

for i in p:
    a = i**74
    if not m % a:
        ans.add(a)
        break

for a,b in permutations(p,2):
    c = a**2*b**24
    if not m % c:
        ans.add(c)
    c = a**4*b**14
    if not m % c:
        ans.add(c)

for a,b,c in permutations(p, 3):
    d = a**2 * b**4 * c ** 4
    if not m % d:
        ans.add(d)

print(len(ans))

Submission status: Accepted

Solution code:
n = int(input())
x = 1
for i in range(1,n+1):
    x *=i

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

a = factorize(x)
prime= []
num = []
for s in a:
    if s[1]>1:
        prime.append(s[0])
        num.append(s[1])
ans = 0
ab24 = []
ab14 = []
ab4 = []
alls = []
for n,p in zip(num,prime):
    if n>=74:
        ans += 1
    if n>=24:
        ab24.append([p,n])
    if n>=14:
        ab14.append([p,n])
    if n>=4:
        ab4.append([p,n])
    alls.append([p,n])

ans += len(ab24)*(len(alls)-len(ab24)) + len(ab24)*(len(ab24)-1)
ans += len(ab14)*(len(ab4)-len(ab14)) + len(ab14)*(len(ab14)-1)
ans += len(ab4)*(len(ab4)-1)*(len(alls)-2)/2
print(int(ans))

Submission status: Accepted

Solution code:
N = int(input())
from math import ceil, sqrt, factorial
from itertools import permutations
def eratosthenes(n):
    l = [1 for i in range(n+1)]
    l[0] = l[1] = 0
    for i in range(2, ceil(sqrt(n))):
        if l[i] == 0: continue
        for j in range(i*2, n+1, i):
            l[j] = 0
    return l

m = factorial(N)
ans = set()

p = eratosthenes(530)

p = [i for i,v in enumerate(p) if v ]

for i in p:
    a = i**74
    if not m % a:
        ans.add(a)
        break

for a,b in permutations(p,2):
    c = a**2*b**24
    if not m % c:
        ans.add(c)
    c = a**4*b**14
    if not m % c:
        ans.add(c)

for a,b,c in permutations(p, 3):
    d = a**2 * b**4 * c ** 4
    if not m % d:
        ans.add(d)

print(len(ans))

Submission status: Accepted

Solution code:
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b

n = getN()
def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac

yaku = []
for i in range(2,n+1):
    yaku = yaku + (primes(i))


from collections import defaultdict
yakunum = defaultdict(int)
for i in yaku:
    yakunum[i] += 1


over2, over4, over14, over24, over74 = 0,0,0,0,0
for i in yakunum.values():

    if i > 1:
        over2 += 1
    if i > 3:
        over4 += 1
    if i > 13:
        over14 += 1
    if i > 23:
        over24 += 1
    if i > 73:
        over74 += 1

#print(over2, over4, over14, over24, over74 )
ans = over74 + (over24*over2)-(over24) + (over14*over4)-over14 + ((over4)*(over4-1)*(over2-2))//2

print(ans)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
# 0以上整数x「未満」の素数をリストに格納して返す
n = int(input())
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0  # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]
pr = primes(100)
q = math.factorial(n)
di = {}
di = defaultdict(int)
for i in pr:
    while q % i == 0:
        q = q // i
        di[i] += 1
co = 0
do1 = 0
eo1= 0
do2 = 0
eo2= 0
do3 = 0
eo3= 0
for k in di:
    if di[k] >= 24:
        do1 += 1
    if di[k] >= 2:
        eo1 += 1
if do1 >= 1 and eo1 >= 2:
    co += do1 * (eo1 - 1)
for k in di:
    if di[k] >= 14:
        do2 += 1
    if di[k] >= 4:
        eo2 += 1
if do2 >= 1 and eo2 >= 2:
    co += do2 * (eo2 - 1)
for k in di:
    if di[k] >= 4:
        do3 += 1
    if di[k] >= 2:
        eo3 += 1
if do3 >= 2 and eo3 >= 3:
    co += comb(do3,2) * (eo3 - 2)
for k in di:
    if di[k] >= 74:
        co += 1
print(co)

Submission status: Accepted

Solution code:
import itertools

N = int(input())
b = [False] * 101
prime = []
b[1] = True

for i in range(2, 101):
    if b[i]:
        continue
    k = i + i
    while k < 101:
        b[k] = True
        k += i

    prime.append(i)

p = [[0] * len(prime) for i in range(N + 1)]

for i in range(1, N + 1):
    n = i
    for j in range(len(prime)):
        while n % prime[j] == 0:
            p[i][j] += 1
            n //= prime[j]

pp = [0] * len(prime)

for i in range(len(prime)):
    for j in range(1, N + 1):
        pp[i] += p[j][i]

ans = 0

for x in pp:
    if x >= 74:
        ans += 1

for a in list(itertools.combinations(range(len(prime)), 2)):
    if pp[a[0]] >= 24 and pp[a[1]] >= 2:
        ans += 1
    if pp[a[0]] >= 2 and pp[a[1]] >= 24:
        ans += 1
    if pp[a[0]] >= 14 and pp[a[1]] >= 4:
        ans += 1
    if pp[a[0]] >= 4 and pp[a[1]] >= 14:
        ans += 1

for a in list(itertools.combinations(range(len(prime)), 3)):
    if pp[a[0]] >= 2 and pp[a[1]] >= 4 and pp[a[2]] >= 4:
        ans += 1
    if pp[a[0]] >= 4 and pp[a[1]] >= 2 and pp[a[2]] >= 4:
        ans += 1
    if pp[a[0]] >= 4 and pp[a[1]] >= 4 and pp[a[2]] >= 2:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import takewhile


def prime_cnt(x):
    y = x
    ret = 0
    while y <= n:
        z = y
        while True:
            ret += 1
            z //= x
            if z == 0 or z % x:
                break
        y += x
    return ret


n = int(input())
ps = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
pc = list(map(prime_cnt, ps))

l2 = len(list(takewhile(lambda x: x >= 2, pc)))
l4 = len(list(takewhile(lambda x: x >= 4, pc)))
l14 = len(list(takewhile(lambda x: x >= 14, pc)))
l24 = len(list(takewhile(lambda x: x >= 24, pc)))
l74 = len(list(takewhile(lambda x: x >= 74, pc)))
ans = l4 * max(0, l4 - 1) * max(0, l2 - 2) // 2
ans += l14 * max(0, l4 - 1)
ans += l24 * max(0, l2 - 1)
ans += l74

print(ans)

Submission status: Accepted

Solution code:
def is_prime(i):
  if i < 2:
    return False
  for j in range(2, i):
    if i % j == 0:
      return False
  return True
primes = [i for i in range(100) if is_prime(i)]

n = int(input())
dic = {}
for i in primes:
  dic[i] = 0

def soinsuubunnkai(x, dic):
  while True:
    for i in primes:
      if x % i == 0:
        dic[i] += 1
        x //= i
        break
    else:
      break

for i in range(1, n + 1):
  soinsuubunnkai(i, dic)

s75 = len([i for i in list(dic.values()) if i >= 74])
s25 = len([i for i in list(dic.values()) if i >= 24])
s15 = len([i for i in list(dic.values()) if i >= 14])
s5 = len([i for i in list(dic.values()) if i >= 4])
s3 = len([i for i in list(dic.values()) if i >= 2])
ans = 0
ans += s75
ans += s25 * (s3 - 1)
ans += s15 * (s5 - 1)
ans += (s5 * (s5 - 1)) // 2 * (s3 - 2)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
def inpl(): return list(map(int, input().split()))

N = int(input())
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]
X = [0]*25
for i in range(1, N+1):
    for j in range(25):
        while i % P[j] == 0:
            i = i//P[j]
            X[j] += 1

ans = 0

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

over = defaultdict(set)
for i in range(25):
    for j in [2, 4, 14, 24]:
        if X[i] >= j:
            over[j].add(i)

for o2 in over[2]:
    o4 = over[4] - set([o2])
    o24 = over[24] - set([o2])
    ans += len(o4) * (len(o4)-1) // 2
    ans += len(o24)

for o4 in over[4]:
    o14 = over[14] - set([o4])
    ans += len(o14)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
L={}
cnt = 0
for i in range(2, N+1):
    X=i
    f = 0
    while f == 0:
        for j in range(2, X+1):
            if X % j == 0:
                if j in L:
                    L[j]=L[j]+1
                else:
                    L[j]=1
                X=int(X/j)
                if X==1:
                    f = 1
                break

C75 = 0
C25 = 0
C15 = 0
C5 = 0
C3 = 0
for i in L.values():
    if i >= 74:
        C75 += 1
    if i >= 24:
        C25 += 1
    if i >= 14:
        C15 += 1
    if i >= 4:
        C5 += 1
    if i >= 2:
        C3 += 1
cnt = C75
cnt += C25 * (C3-1)
cnt += C15 * (C5-1)
cnt += int(C5 * (C5-1) / 2 * (C3-2))
print(cnt)
# 3 5 15 25 75
# 3 * 5 * 5

Submission status: Accepted

Solution code:
n = int(input())
factor = [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]
factor_num = [0] * len(factor)
if n <= 9:
	print(0)
else:
	for i in range(2, n+1):
		for j in range(len(factor)):
			cnt = 0
			while i % factor[j] == 0:
				cnt += 1
				i = i // factor[j]
			factor_num[j] += cnt

	two_three = 0
	over_four = 0
	over_fourteen = 0
	over_twentyfour = 0
	over_seventyfour = 0

	for i in range(len(factor)):
		if 2 <= factor_num[i] <= 3:
			two_three += 1
		elif factor_num[i] >= 4:
			over_four += 1
			if factor_num[i] >= 14:
				over_fourteen += 1
			if factor_num[i] >= 24:
				over_twentyfour += 1
			if factor_num[i] >= 74:
				over_seventyfour += 1

	ans = two_three * (over_four * (over_four - 1) // 2) + over_four * ((over_four - 1) * (over_four - 2) // 2)
	ans += over_fourteen * (over_four - 1) + over_twentyfour * (two_three + over_four - 1)
	ans += over_seventyfour

	print(ans)

Submission status: Accepted

Solution code:
import types, math, operator
import numpy as np
from math import sqrt
from collections import Counter
from itertools import product
from functools import reduce
class PrimeUtils:
    @staticmethod
    def _has_numpy():
        g = globals()
        m = g.get('np')
        if m is not None and isinstance(m, types.ModuleType):
            return  m.__name__ == 'numpy'
        return False
    @staticmethod
    def _primes_sieve_pp(n):
        sieve = [True] * (n + 1)
        for i in range(2, int(sqrt(n)) + 1):
            if sieve[i]:
                for j in range(i * i, n + 1, i):
                    sieve[j] = False
        return [i for i, x in enumerate(sieve[2:], 2) if x]
    @staticmethod
    def _primes_sieve_np(n):
        sieve = np.ones(n + 1, np.bool)
        sieve[0] = sieve[1] = False
        for i, v in enumerate(sieve[2:int(sqrt(n)) + 1], 2):
            if v: sieve[i*i::i] = False
        return np.nonzero(sieve)[0]
    @staticmethod
    def _primes_sieve_np_fast(n):
        n += 1
        sieve = np.ones(n//3 + (n%6 == 2), dtype=np.bool)
        check_upper = int(sqrt(n)) // 3
        for i, v in enumerate(sieve[1:check_upper + 1], 1):
            if v:
                k = (3*i + 1) | 1
                sieve[k* k           //3::2*k] = False
                sieve[k*(k-2*(i&1)+4)//3::2*k] = False
        sieve[0] = False
        return np.r_[2,3,((3*np.nonzero(sieve)[0] + 1)|1)]
    @classmethod
    def primes_sieve(cls, n):
        if cls._has_numpy():
            return cls._primes_sieve_np_fast(n)
        else:
            return cls._primes_sieve_pp(n)
    # Prime Factor Decomposition
    @classmethod
    def pfd(cls, primes, n):
        # primes = cls.primes_sieve(n)

        factors = []
        cur = n
        for p in primes:
            while True:
                div, rem = divmod(cur, p)
                if rem == 0:
                    factors.append(p)
                    cur = div
                else:
                    break
        assert(cur == 1)
        return factors
    # List up aliquots
    @classmethod
    def aliquots(cls, n):
        pf = cls.pfd(n)
        pfc = Counter(pf)
        ppv = [[pow(p, i) for i in range(n+1)] for p,n in pfc.items()]
        if not ppv:
            return (1,)
        else:
            return map(lambda x: reduce(operator.imul, x), product(*ppv))

    @classmethod
    def aliquots_n(cls, n):
        pf = cls.pfd(n)
        pfc = Counter(pf)
        ppv = [[pow(p, i) for i in range(n+1)] for p,n in pfc.items()]
        if not ppv:
            return 1
        else:
            return reduce(operator.imul, [len(x) for x in ppv])

import math
fact = math.factorial
N = int(input())

from collections import Counter
primes = PrimeUtils.primes_sieve(N)

cc = Counter()
for n in range(N):
    cc += Counter(PrimeUtils.pfd(primes, n + 1))

cn = Counter()
for n in cc.values():
    if n >= 2:
        cn[3] += 1
    if n >= 4:
        cn[5] += 1
    if n >= 14:
        cn[15] += 1
    if n >= 24:
        cn[25] += 1
    if n >= 74:
        cn[75] += 1
print(sum([
      cn[75],
      cn[15] * (cn[5] - 1) ,
      cn[25] * (cn[3] - 1) ,
      max(0, (cn[3] - cn[5])) * max(0, cn[5]) * max(0, (cn[5] - 1)) // 2,
      cn[5] * max(0, (cn[5] - 1)) * max(0, (cn[5] - 2)) // 2
      ]))

Submission status: Accepted

Solution code:
import copy
def prime_decomposition(n, table):
  i = 2
  while i * i <= n:
    c = 0
    while n % i == 0:
      n /= i
      c+=1
    if c!=0:
        if i not in table:
            table[i] = c
        else:
            table[i] += c
    i += 1
  if n > 1:
    if int(n) not in table:
        table[int(n)] = 1
    else:
        table[int(n)] += 1
  return table

table = {}
for i in range(int(input().strip())):
    table = prime_decomposition(i+1, table)

def find_224(ns, ttt, depth, counter):
    n_ttt = copy.deepcopy(ttt)
    if ns[depth] == 4:
        ccc = 0
        for i in n_ttt:
            if n_ttt[i] >= 4:
                ccc += 1
        return (ccc * (ccc -1) )// 2

    counter = 0
    for i in ttt:
        if ttt[i] >= ns[depth]:
            tmp = n_ttt[i]
            del n_ttt[i]
            counter += find_224(ns, n_ttt, depth + 1, counter)
            n_ttt[i] = tmp
    return counter

def find_n(ns, ttt, depth, counter):
    n_ttt = copy.deepcopy(ttt)
    counter = 0
    for i in ttt:
        if ttt[i] >= ns[depth]:
            if len(ns) == depth + 1:
                counter += 1
            else:
                tmp = n_ttt[i]
                del n_ttt[i]
                counter += find_n(ns, n_ttt, depth + 1, counter)
                n_ttt[i] = tmp
    return counter

# 553
res = 0
res += find_224([2, 4], table, 0, 0)

res += find_n([14, 4], table, 0, 0)
res += find_n([24, 2], table, 0, 0)
res += find_n([74], table, 0, 0)
print(res)

Submission status: Accepted

Solution code:
def dfs(f, r):
    if r==1:
        return 1
    if len(f) == 0:
        return 0

#    print(f, r)
    out = dfs(f[1:], r)
    for i in range(1, min(r, f[0][1])+1):
        if r%(i+1) == 0:
            out += dfs(f[1:], r//(i+1))
    return out

N = int(input())
s = 0

fact = {}
for j in range(2, N+1):
    s = 0
    k = j
    while s==0:
        for i in range(2,k+1):
            if k%i==0:
                k=int(k/i)
                if k==1:
                    s=1
                fact[i] = fact.get(i, 0)+1
                break

fact = list(fact.items())
res = dfs(fact, 75)
print(res)

Submission status: Accepted

Solution code:
n = int(input())
factor = [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]
factor_num = [0] * len(factor)
if n <= 9:
	print(0)
else:
	for i in range(2, n+1):
		for j in range(len(factor)):
			cnt = 0
			while i % factor[j] == 0:
				cnt += 1
				i = i // factor[j]
			factor_num[j] += cnt

	#print(factor_num)

	two_three = 0
	over_four = 0
	over_fourteen = 0
	over_twentyfour = 0
	over_seventyfour = 0

	for i in range(len(factor)):
		if 2 <= factor_num[i] <= 3:
			two_three += 1
		elif factor_num[i] >= 4:
			over_four += 1
			if factor_num[i] >= 14:
				over_fourteen += 1
			if factor_num[i] >= 24:
				over_twentyfour += 1
			if factor_num[i] >= 74:
				over_seventyfour += 1

	#print(two_three, over_four, over_fourteen, over_twentyfour, over_seventyfour)

	ans = two_three * (over_four * (over_four - 1) // 2) + over_four * ((over_four - 1) * (over_four - 2) // 2)
	ans += over_fourteen * (over_four - 1) + over_twentyfour * (two_three + over_four - 1)
	ans += over_seventyfour

	print(ans)

Submission status: Accepted

Solution code:
import math
#import sympy
n=int(input())
a=math.factorial(n)
#print(a)
#a=32400

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors
ps=prime_factors(a)
sy={}
for i in ps:
    if i not in sy:
        sy[i]=1
    else:
        sy[i]+=1
#aaaaaaaaaaa
#sy=sympy.factorint(a)
count75=0
count25=0
count15=0
count5=0
count3=0
for k in sy.values():
    #print(k)
    if k+1>=75:
        count75+=1
    if k+1>=25:
        count25+=1
    if k+1>=15:
        count15+=1
    if k+1>=5:
        count5+=1
    if k+1>=3:
        count3+=1

#print(count75)
#print(count25*(count3-1))
#print(count15*(count5-1))
#print((count5*(count5-1)*(count3-2))/2)
print(int(count75+count25*(count3-1)+count15*(count5-1)+(count5*(count5-1)*(count3-2))/2))

Submission status: Accepted

Solution code:
N = int(raw_input())
prime_in_N = {}
for n in range(2, N+1):
  while True:
    bn = n
    for p in (2, 3, 5, 7):
      if n % p == 0:
        n /= p
        if not p in list(prime_in_N.keys()):
          prime_in_N[p] = 0
        prime_in_N[p] += 1
    if bn == n:
      break
  if n > 7:
    if not n in list(prime_in_N.keys()):
      prime_in_N[n] = 0
    prime_in_N[n] += 1
ans = 0
for a in list(prime_in_N.keys()):
  if prime_in_N[a] >= 74:
	ans += 1
for a in list(prime_in_N.keys()):
  if prime_in_N[a] >= 2:
    for b in set(prime_in_N.keys())-set([a]):
      if prime_in_N[b] >= 24:
        ans += 1
for a in list(prime_in_N.keys()):
  if prime_in_N[a] >= 4:
    for b in set(prime_in_N.keys())-set([a]):
      if prime_in_N[b] >= 14:
        ans += 1
tmp_ans = 0
for a in list(prime_in_N.keys()):
  if prime_in_N[a] >= 2:
    for b in set(prime_in_N.keys())-set([a]):
      if prime_in_N[b] >= 4:
        for c in set(prime_in_N.keys())-set([a])-set([b]):
      		if prime_in_N[c] >= 4:
        		tmp_ans += 1
print ans+tmp_ans/2

Submission status: Accepted

Solution code:
import math

n = int(input())
pt = [True for i in range(n + 1)]
ps = []
for i in range(2, n + 1):
    if pt[i]:
        ps.append(i)
        m = i * 2
        while m <= n:
            pt[m] = False
            m += i

ans = 0
fa = math.factorial(n)

for p in ps:
    po = p ** 74
    if fa % po == 0:
        ans += 1
    for q in ps:
        if q == p:
            continue
        po = (p ** 2) * (q ** 24)
        if fa % po == 0:
            ans += 1
        po = (p ** 4) * (q ** 14)
        if fa % po == 0:
            ans += 1
        for r in ps:
            if r == p or r <= q:
                continue
            po = (p ** 2) * (q ** 4) * (r ** 4)
            if fa % po == 0:
                ans += 1

print(ans)