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

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

M = N
fac_lst = []
for i in prime:
    count = 0
    M = N
    while M % i == 0:
        M = M // i
        count += 1
    fac_lst.append(count)
    
count0, count1, count2, count3, count4 = 0, 0, 0, 0,0
for i in fac_lst:
    if i >= 74:
        count0 += 1
        count1 += 1
        count2 += 1
        count3 += 1
        count4 += 1
    elif i >= 24:
        count1 += 1
        count2 += 1
        count3 += 1
        count4 += 1
    elif i >= 14:
        count2 += 1
        count3 += 1
        count4 += 1
    elif i >= 4:
        count3 += 1
        count4 += 1
    elif i >= 2:
        count4 += 1
count_lst = [count0, count1, count2, count3, count4]

ans0 = count_lst[0]
ans1 = count_lst[1] * (count_lst[4] - 1)
ans2 = count_lst[2] * (count_lst[3] - 1)
ans3 = (count_lst[3]*(count_lst[3]-1) // 2) * (count_lst[4] - 2)
if ans1 < 0:
    ans1 = 0
if ans2 < 0:
    ans2 = 0
if ans3 < 0:
    ans3 = 0
print(ans0+ans1+ans2+ans3)

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):
        # ひたすら割り算を繰り返す
        # 2で割り続ければ、4で割ろうとした時には2で割れない数になっている
        # 自動的に素因数分解ができる
        while cur % j == 0:
            e[j] += 1
            cur //= j

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

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

Submission status: Accepted

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

class Prime:
    seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

    def is_prime(self, n):
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_bf(n)
        else:
            return self.is_prime_mr(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

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

    def is_prime_mr(self, n):
        d = n - 1
        while d % 2 == 0:
            d //= 2

        witnesses = self.get_witnesses(n)

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y ** 2) % n
                d *= 2

            if y != n - 1 and d % 2 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 38255123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            a, b = b, a
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed+1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes

prime = Prime()

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

    prime = Prime()

    factors = {}

    for i in range(2, N + 1):
        f = prime.find_factors(i)
        for k, v in f.items():
            if k in factors:
                factors[k] += v
            else:
                factors[k] = v

    t = factors.values()

    r = 0

    g75 = len([v for v in t if 74 <= v])
    g25 = len([v for v in t if 24 <= v])
    g15 = len([v for v in t if 14 <= v])
    g5 = len([v for v in t if 4 <= v])
    g3 = len([v for v in t if 2 <= v])

    # 75 = 75
    r += g75

    # 75 = 25 * 3
    r += g25 * (g3 - 1)

    # 75 = 15 * 5
    r += g15 * (g5 - 1)

    # 75 = 5 * 5 * 3
    r += g5 * (g5 - 1) // 2 * (g3 - 2)


    print(r)


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, N + 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())
Nprime = [x for x in range(2,N+1) if (x%2 !=0 and x%3!=0 and x%5!=0 and x%7!=0)]
Nprime = [2,3,5,7] + Nprime
F = []
for i,j in enumerate(Nprime):
    number = N
    while number != 0:
        F.append(0)
        F[i] += number//j
        number = number//j

more_two = 0
more_four = 0
ans1 = 0
ans = 0

for i in F:
    if i >= 2:
        more_two += 1
    if i >= 4:
        more_four += 1

for i in F:
    if i >= 4:
        ans1 += (more_four-1)*(more_two-2)
    else:
        continue
    if i >= 14:
        ans += more_four - 1
    if i >= 24:
        ans += more_two - 1
    if i >= 74:
        ans += 1

ans += ans1//2

print(ans)

Submission status: Accepted

Solution code:
def era(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(2*i, n + 1, i):
                table[j] = 1
    
    return prime_list

def f(n):
    cnt = 0
    for i in data:
        if i[1] >= n-1:
            cnt += 1
    return cnt
 
N = int(input())
s = era(N)
data = []
 
for i in s:
    k = i
    c = 0
    while N // k >= 1:
        c += N // k
        k = k*i
 
    data.append([i,c])
 

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

Submission status: Accepted

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

cnt = Counter()


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

for i in range(1, N+1):
    factor(i)

#cnt = list(cnt.values())[::-1]
cnt = sorted(cnt.values())

cnt_over_n = lambda x: len(cnt)-bisect.bisect_left(cnt, x)
tmp2 = cnt_over_n(2)
tmp4 = cnt_over_n(4)
tmp14 = cnt_over_n(14)
tmp24 = cnt_over_n(24)
tmp74 = cnt_over_n(74)

ans = 0
ans += (tmp2-tmp4)*tmp4*(tmp4-1)//2 + tmp4*(tmp4-1)*(tmp4-2)//6*3
ans += (tmp4-tmp14)*tmp14 + tmp14*(tmp14-1)
ans += (tmp2-tmp24)*tmp24 + tmp24*(tmp24-1)
ans += tmp74
print(ans)

Submission status: Accepted

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

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

s=[]

for i in range(1,n+1):
  s=s+(prime_decomposition(i))

count2=0
count4=0
sumation=0
for i in range(1,n+1):
  if s.count(i)==2 or s.count(i)==3:
    count2 +=1
  elif s.count(i) >3:
    count4 +=1

sumation += count4*(count4-1)/2*(count2+count4-2)

count2=0
count4=0
for i in range(1,n+1):
  if s.count(i)>=24:
    count2 +=1
  elif s.count(i) >=2:
    count4 +=1
    
sumation += count2*(count2+count4-1)

count2=0
count4=0
for i in range(1,n+1):
  if s.count(i)>=14:
    count2 +=1
  elif s.count(i) >=4:
    count4 +=1
    
sumation += count2*(count2+count4-1)

count2=0
count4=0
for i in range(1,n+1):
  if s.count(i)>=74:
    count2 +=1
    
sumation += count2

print(int(sumation))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

N = input()
F = defaultdict(int)

def factorization(n):
    f=defaultdict(int)
    a = n
    for k in range(2, n+1):
        while a%k==0:
            f[k]+=1
            a/=k
    return f


def solve():
    A = F.values()
    B = F.keys()
    # (24, 2)
    n = len(A)
    s1 = set()
    for i in range(n):
        a = A[i]
        if a >= 24:
            for j in range(n):
                if i == j: continue
                if A[j] >= 2:
                    a = B[i]
                    b = B[j]
                    s1.add(a**24 + b**2)
    # (14, 4)
    n = len(A)
    s2 = set()
    for i in range(n):
        a = A[i]
        if a >= 14:
            for j in range(n):
                if i == j: continue
                if A[j] >= 4:
                    a = B[i]
                    b = B[j]
                    s2.add(a**14 + b**4)

    # (4, 4, 2)
    n = len(A)
    s3 = set()
    for i in range(n):
        a = A[i]
        if a >= 4:
            for j in range(n):
                if i == j: continue
                if A[j] >= 4:
                    for k in range(n):
                        if k == i or k == j: continue
                        if A[k] >= 2:
                            a = B[i]
                            b = B[j]
                            c = B[k]
                            s3.add(a**4 + b**4+c**2)

    # (74)    
    n = len(A)
    s4 = set()
    for i in range(n):
        a = A[i]
        if a >= 74:
            s4.add(a**74)                    

    return len(s1) + len(s2) + len(s3) + len(s4)

    




for n in range(2, N+1):
    f = factorization(n)
    for k, v in f.iteritems():
        F[k] += v

print(solve())

Submission status: Accepted

Solution code:
import collections
import itertools
import math


N = int(input())


def get_prime_factorized(N):
    R = []
    b, e = 2, 0
    while b ** 2 <= N:
        while N % b == 0:
            N  = N // b
            e += 1
        if e > 0:
            R.append([b, e])
        b, e = b + 1, 0
    if N > 1:
        R.append([N, 1])
    return R


def n_C_r(n, r):
    return int(math.factorial(n) / math.factorial(r) / math.factorial(n-r))


if N > 9:
    L = [l[1]+1 for l in get_prime_factorized(math.factorial(N))]
    L = [[3, 5, 15, 25, 75] if l >= 75 else [3, 5, 15, 25] if l >= 25 else [3, 5, 15] if l >= 15 else [3, 5] if l >= 5 else [3] if l >= 3 else [1] for l in L]
    L = [l for l in L if l != [1]]
    L = list(itertools.chain.from_iterable(L))
    C = collections.Counter(L)

    R = C[75] + n_C_r(C[5], 2) * n_C_r(C[3]-2, 1) + C[25] * (C[3] - 1) + C[15] * (C[5] - 1)

    print(R)
else:
    print(0)

Submission status: Accepted

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

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

c = tuple(filter(lambda x: x > 0, e))  # 素因数の指数

dp = [[0 for _ in range(75 + 1)] for _ in range(len(c) + 1)]  # dp[素因数のidx][約数の個数] = 条件を満たす個数
dp[0][1] = 1

i = 1
for cc in c:
    for j in range(1, 75 + 1):
        k = 0  # 指数のうち使う個数
        while j * (k + 1) <= 75 and k <= cc:
            dp[i][j * (k + 1)] += dp[i - 1][j]
            k += 1
    i += 1

# print(c)
print(dp[len(c)][75])

Submission status: Accepted

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


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

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

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

Submission status: Accepted

Solution code:
n = int(input())

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

pf = nprf(n)

def f(n):
    count = 0
    for v in pf.values():
        if v >= n-1:
            count += 1
    return count

f1 = f(75)
f2 = f(25) * (f(3)-1)
f3 = f(15) * (f(5)-1)
f4 = f(5) * (f(5)-1) //2 * (f(3)-2)

print(f1 + f2 + f3 + f4)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# AtCoder Beginner Contest 114：D - 756


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


def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]


def ncm(n, m):
    if n<m:
        return 0
    a = 1
    for i in range(m):
        a *= (n-i)
    for i in range(m):
        a /= (m-i)
    return a


def main():
    N = int(raw_input().strip())

    # f = [[], []]
    f = []
    for i in range(2, N+1):
        f.append(factorize(i))
    # print f

    ff = [0]*100
    # print ff
    for fp in f:
        for fpp in fp:
            ff[fpp[0]] += fpp[1]
    # print ff

    '''
      5, 4, 3, 0, 5, 2, 4
    a *  *        *     * >= 4
    b *  *  *     *  *  * >= 2
    '''
    # (4+1) * (4+1) * (2+1) = 75
    # aC2 * (b-2)
    a = 0
    b = 0
    for fn in ff:
        if fn >= 4:
            a += 1
        if fn >= 2:
            b += 1
    n1 = ncm(a, 2) * (b-2)

    # (24+1)*(2+1) = 75
    # a * (b-1)
    a = 0
    b = 0
    for fn in ff:
        if fn >= 24:
            a += 1
        if fn >= 2:
            b += 1
    n2 = a * (b-1)

    # (14+1)*(4+1) = 75
    # a * (b-1)
    a = 0
    b = 0
    for fn in ff:
        if fn >= 14:
            a += 1
        if fn >= 4:
            b += 1
    n3 = a * (b-1)

    # (74+1) = 75
    # a
    a = 0
    for fn in ff:
        if fn >= 74:
            a += 1
    n4 = a

    print n1+n2+n3+n4


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

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

    print(check(75, e) +
          check(25, e) * (check(3, e) - 1) +
          check(15, e) * (check(5, e) - 1) +
          check(5, e) * (check(5, e) - 1) * (check(3, e) - 2) // 2)


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:
#!/usr/bin/env python3

from functools import lru_cache

def prime_factor_of_fact(n):
    di = {}
    for i in range(1, n + 1):
        pf = prime_factor(i)
        for p in pf:
            if p not in di:
                di[p] = 1
            else:
                di[p] += 1
    return di

@lru_cache()
def prime_factor(n):
    if n == 1:
        return []
    for i in range(2, n + 1):
        if n % i == 0:
            res = prime_factor(n // i) + [i]
            break
    return res

def shichigo_su(pff):
    have_seventyfour = len([k for k in pff if pff[k] >= 74])
    have_twentyfour = len([k for k in pff if pff[k] >= 24])
    have_fourteen = len([k for k in pff if pff[k] >= 14])
    have_four = len([k for k in pff if pff[k] >= 4])
    have_two = len([k for k in pff if pff[k] >= 2])
    if have_four >= 2 and have_two >= 3:
        res = ((have_four * (have_four - 1)) // 2) * (have_two - 2) \
            + have_fourteen * (have_four - 1) \
            + have_twentyfour * (have_two - 1) \
            + have_seventyfour
        return res
    else:
        return 0

def main():
    n = int(input())
    pff = prime_factor_of_fact(n)
    print(shichigo_su(pff))

main()

Submission status: Accepted

Solution code:
# coding: utf-8

from collections import Counter

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]
II = lambda: int(input())
MI = lambda: map(int, input().split())

def factorization_pow(n):
    facts = Counter()
    for i in range(2, n + 1):
        for p in PRIMES:
            while i % p == 0:
                facts[p] += 1
                i = i // p
    return facts

C2 = lambda n: n * (n-1) // 2

def main():
    N = II()
    f = factorization_pow(N)
    LC = lambda v: len(list(filter(lambda x: x >= v, f.values())))
    return LC(74) + LC(24) * (LC(2) - 1) + LC(14) * (LC(4) - 1) + C2(LC(4)) * (LC(2) - 2)

if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
n = int(input())
yakusu = [0]*105
for num in range(1,n+1):
    for i in range(2,n+1):
        while(num%i==0):
            yakusu[i] += 1
            num//=i
        if num == 1:
            break

over = [0]*100
for i in range(1,n+1):
    if(yakusu[i] >= 2):
        over[2]+=1
    if(yakusu[i] >= 4):
        over[4]+=1
    if(yakusu[i] >= 14):
        over[14]+=1
    if(yakusu[i] >= 24):
        over[24]+=1
    if(yakusu[i] >= 74):
        over[74]+=1

ans = over[74]+over[14]*(over[4]-1) + over[24]*(over[2]-1) + over[4]*(over[4]-1)*(over[2]-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 collections

n = int(input())

counts = collections.defaultdict(int)
for x in range(2, n + 1):
    for y in range(2, n + 1):
        while x % y == 0:
            counts[y] += 1
            x //= y

def f(a):
    return sum(1 for b in counts if counts[b] >= a - 1)

answer = f(75) \
           + f(5) * (f(5) - 1) * (f(3) - 2) // 2 \
           + f(15) * (f(5) - 1) \
           + f(25) * (f(3) - 1)
print(answer)

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:
N = int(input())
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

two = sum(p<=N//2 for p in primes) # 2
four = sum(p<=N//4 for p in primes) if N>=12 else sum([N>=9, N>=6]) # 4
ft = sum([N>=91, N>=60, N>=30, N>=16]) # 14
tf = sum([N>=100, N>=54, N>=28]) # 24
sf = N>=78 # 74

tff = four * (four-1) * (two-2) // 2 # 2,4,4
ttf = tf * (two-1) # 2,24
fft = ft * (four-1) # 4,14
sfo = sf # 74

print(tff+ttf+fft+sfo)

Submission status: Accepted

Solution code:
n = int(input())

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

def c(P, m):
    count = 0
    for i in P:
        if P[i] >= m - 1:
            count += 1
    return count   
    
P = nprf(n)

f75 = c(P, 75)
f253 = c(P, 25) * (c(P, 3) - 1)
f155 = c(P, 15) * (c(P, 5) - 1)
f553 = int(c(P, 5) * (c(P, 5) - 1) * (c(P, 3) - 2) * 0.5)

print(f75 + f253 + f155 + f553)

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
N = int(input())

p = [i for i in range(2,N+1)]
q = []

for i in p:
    for j in range(2,i):
        if i%j==0:
            q.append(i)
            break
        
p = list(set(p)-set(q))

def div(n):
    ret=0
    a=math.factorial(N)
    while a%n == 0:
        a//=n
        ret+=1
    return ret

Ans=0

for n in p:
    if div(n)>=74:
        Ans+=1

for n in p:
    if div(n)>=24:
        for m in p:
            if div(m)>=2 and n!=m:
                Ans += 1

        
for n in p:
    if div(n)>=14:
        for m in p:
            if div(m)>=4 and n!=m:
                Ans += 1

for n in p:
    if div(n)>=2:
        for m in p:
            if n!=m and div(m)>=4:
                for l in p:
                    if l!=n and l>m and div(l)>=4:
                        Ans +=1

print(Ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Jan  3 10:20:42 2019

@author: Yamazaki Kenichi
"""

N = int(input())

prime = [2]
for j in range(3,100):
    if all(j % i != 0 for i in prime) :
        prime.append(j)

N1 = 1
for i in range(1,N+1):
    N1 *= i 

prime1 = []
for j in prime:
    temp = 0
    while N1 % pow(j,temp) ==0:
        temp += 1
    prime1.append(temp-1)

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

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Jan  3 10:20:42 2019

@author: Yamazaki Kenichi
"""

N = int(input())

prime = [2]
for j in range(3,100):
    if all(j % i != 0 for i in prime) :
        prime.append(j)

N1 = 1
for i in range(1,N+1):
    N1 *= i 

prime1 = []
a02,a04,a14,a24,a74 =0,0,0,0,0
for j in prime:
    temp = 0
    while N1 % pow(j,temp) ==0:
        temp += 1
    a02 += 1 if temp > 2 else 0
    a04 += 1 if temp > 4 else 0
    a14 += 1 if temp > 14 else 0
    a24 += 1 if temp > 24 else 0
    a74 += 1 if temp > 74 else 0    
    prime1.append(temp)

ans = a74 +a24*(a02-1) +a14*(a04-1) +a04*(a04-1)//2*(a02-2)



print(ans)

Submission status: Accepted

Solution code:
N = int(input())

d = [0] * 100
for n in range(1, N+1):
  for p in range(2, 100):
    while n % p == 0:
      d[p] += 1
      n /= p

ans = 0

# 75 = 5 * 5 * 3
for i in range(100):
  for j in range(100):
    for k in range(100):
      if i < j and i != k and j != k:
        if d[i] >= 4 and d[j] >= 4 and d[k] >= 2:
          ans += 1

# 25 * 3
for i in range(100):
  for j in range(100):
    if i != j:
      if d[i] >= 24 and d[j] >= 2:
        ans += 1

# 5 * 15
for i in range(100):
  for j in range(100):
    if i != j:
      if d[i] >= 4 and d[j] >= 14:
        ans += 1

# 75
for i in range(100):
  if d[i] >= 74:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
def getPrimelist(num):
    if num == 1:
        return([])
    primelist = []
    limit = int(num ** 0.5)
    templist = [i for i in range(2, num + 1)]
    while True:
        p = templist[0]
        if limit < p:
            return primelist + templist
        primelist.append(p)
        templist = [i for i in templist if i % p != 0]

def getfactorsdict(num, power = {}):
    primelist = getPrimelist(int(num ** 0.5))
    for prime in primelist:
        while num % prime == 0:
            if prime in power.keys():
                power[prime] += 1
            else:
                power[prime] = 1
            num //= prime
    if num > 1:
        if num in power.keys():
            power[num] += 1
        else:
            power[num] = 1
    return(power)

N = int(input())
fd = {}
for i in range(1, N + 1):
    fd = getfactorsdict(i, fd)

c75 = 0; c25 = 0; c15 = 0; c5 = 0; c3 = 0
for v in fd.values():
    if v >= 74:
        c75 += 1
    if v >= 24:
        c25 += 1
    if v >= 14:
        c15 += 1
    if v >= 4:
        c5 += 1
    if v >= 2:
        c3 += 1

ans = c75 #75
ans += c25 * (c3 - 1) #25 * 3
ans += c15 * (c5 - 1) #15 * 5
ans += (c5 * (c5 - 1)) // 2 * (c3 - 2) #5 * 5 * 3
print(ans)

Submission status: Accepted

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

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

        return x*mul(x-1)

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

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

Submission status: Accepted

Solution code:
N = int(input())

p = [0] * (N+1)

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

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

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

Submission status: Accepted

Solution code:
def run(N):
  '''
  a^x*b^y*c^yの約数の数が75となるのは(x,y,z)が以下の場合
  (74,0,0), (2,4,4), (24,2,0), (14,4,0)
  N!の素因数分解を行い、各素数のうち上記の取得方法の数を数える
  '''
  # N!を素因数分解
  primes = {1: 1}
  for i in range(2, N+1):
    tmp = i
    for j in range(2, N+1):
      while tmp%j == 0:
        if j in primes.keys():
          primes[j] += 1
        else:
          primes[j] = 1
        tmp /= j
  cnt = 0

  # (74,0,0)
  for i in primes.values():
    if i >= 74:
      cnt += 1

  # (2,4,4)
  cnt4 = 0
  cnt2 = 0
  for i in primes.values():
    if i >= 4:
      cnt4 += 1
    if i >= 2:
      cnt2 += 1
  if cnt4 >= 2:
    cnt += (cnt4*(cnt4-1)//2)*(cnt2-2)

  # (24,2,0)
  cnt24 = 0
  cnt2 = 0
  for i in primes.values():
    if i >= 24:
      cnt24 += 1
    if i >= 2:
      cnt2 += 1
  if cnt24 >= 1:
    cnt += cnt24*(cnt2-1)

  # (14,4,0)
  cnt14 = 0
  cnt4 = 0
  for i in primes.values():
    if i >= 14:
      cnt14 += 1
    if i >= 4:
      cnt4 += 1
  if cnt14 >= 1:
    cnt += cnt14*(cnt4-1)
  return cnt


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

N=int(input())
p_list = [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]
p_c_list = [0 for i in range(len(p_list))]
for i in range(1,1+N):
    for j in range(len(p_list)):
        for k in range(1,8):
            if i%((p_list[j])**k)==0:
                p_c_list[j]+=1
            else:
                break
count=0
for i in range(len(p_list)):
    for j in range(i+1,len(p_list)):
        for k in range(j+1,len(p_list)):
            if min(p_c_list[i],p_c_list[j],p_c_list[k])>=2 and max(p_c_list[i],p_c_list[j],p_c_list[k])>=4:
                if (p_c_list[i]<4 and p_c_list[j]<4) or (p_c_list[k]<4 and p_c_list[j]<4) or (p_c_list[i]<4 and p_c_list[k]<4):
                    count+=0
                elif p_c_list[i]<4 or p_c_list[j] < 4 or p_c_list[k] < 4:
                    count+=1
                else:
                    count+=3

for i in range(len(p_list)):
    if p_c_list[i]>=74:
        count+=1

for i in range(len(p_list)):
    for j in range(i+1,len(p_list)):
        if max(p_c_list[i],p_c_list[j])>=24 and min(p_c_list[i],p_c_list[j])>=2:
            if p_c_list[i]>=24 and p_c_list[j]>=24:
                count+=2
            else:
                count+=1
        if max(p_c_list[i],p_c_list[j])>=14 and min(p_c_list[i],p_c_list[j])>=4:
            if p_c_list[i]>=14 and p_c_list[j]>=14:
                count+=2
            else:
                count+=1        
        
print(count)

Submission status: Accepted

Solution code:
def comb(n, r):
    x = 1
    for i in range(n-r+1, n+1):
        x *= i
    for i in range(1, r+1):
        x //= i
    return x

n = int(input())
x = 1

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

d = dict()
for i in range(2, 100):
    tmp = 0
    while x % i == 0:
        tmp += 1
        x //= i
    if tmp:
        d[i] = tmp

c = [ 0 for _ in range(5)]
for v in d.values():
    if v >= 2:
        c[0] += 1
    if v  >=4:
        c[1] += 1
    if v >= 14:
        c[2] += 1
    if v >= 24:
        c[3] += 1
    if v >= 74:
        c[4] += 1

ans = c[4]
ans += c[3]*(c[0] - 1)
ans += c[2]*(c[1] - 1)
ans += comb(c[1], 2)*(c[0]-2)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
e = [0] * (n+1)

for i in range(2, n+1):
    for j in range(2, i+1):
        while i % j == 0:
            e[j] += 1
            i //= j
            
def count(m):
    return len(list(filter(lambda x: x >= m-1, e)))

a = count(75)
b = count(25) * (count(3) - 1)
c = count(15) * (count(5) - 1)
d = count(5) * (count(5) - 1) * (count(3) - 2) // 2

print(a + b + c + d)