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:
from collections import defaultdict
n = int(input())
if n in [1, 2]:
    print(0)
    exit()

count_primes = defaultdict(int, {})
for m in range(2, n+1):
    p = 2
    while p**2 <= m:
        while m%p == 0:
            m //= p
            count_primes[p] += 1
        p += 1
    if m > 1:
        count_primes[m] += 1
# print(count_primes)

count_div = [0]*100
for _, c in count_primes.items():
    for i in range(c+1):
        count_div[i] += 1
# print(count_div)

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

Submission status: Accepted

Solution code:
#ABC114D-756.py

from math import factorial

N = int(input())
answer = 0

primeN = (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)
amount = []

for i in primeN:
    amount.append(1)

for n in range(N):
    n = n + 1
    for m in range(len(primeN)):
        m = m + 1
        while n >= primeN[-m]:
            if n % primeN[-m] == 0:
                amount[-m] += 1
                n = n // primeN[-m]
            else: break

for i in amount:
    if i >= 75:
        answer += 1

i1, i2 = 0, 0
for i in amount:
    if i >= 15:
        i1 += 1
    elif i >= 5:
        i2 += 1
if i1 >= 1 and i1+i2 >= 2:
    answer += i1 * (i1+i2-1)

i3,i4 = 0, 0
for i in amount:
    if i >= 25:
        i3 += 1
    if i >= 3:
        i4 += 1
if i3 >= 1 and i4 >= 2:
    answer += i3 * (i4-1)

i5, i6 = 0, 0
for i in amount:
    if i >= 5:
        i5 += 1
    if i >= 3:
        i6 += 1
if i5 >= 2 and i6 >= 3:
    answer += (factorial(i5) // 2 // factorial(i5-2)) * (i6-2)

print(answer)

Submission status: Accepted

Solution code:
prime=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
s=[0 for i in range(15)]
N=int(input())
for i in range(15):
  j=1
  while N//(prime[i]**j)>0:
    s[i]+=N//(prime[i]**j)
    j+=1
o3,o5,o15,o25,o75=0,0,0,0,0
for item in s:
  if item>=2:
    o3+=1
    if item>=4:
      o5+=1
      if item>=14:
        o15+=1
        if item>=24:
          o25+=1
          if item>=74:
            o75+=1
ans=[0,0,0,0]
if o75>0:
  ans[0]+=1
if o25>0:
  ans[1]+=o25*(o3-1)
if o15>0:
  ans[2]+=o15*(o5-1)
if o5>1 and o3>2:
  ans[3]+=o5*(o5-1)//2*(o3-2)
print(sum(ans))

Submission status: Accepted

Solution code:
n=int(input())

A=[0 for i in range(n+1)] #素因数分解のリスト

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

#print(A)

B=[]
for i in [2,4,14,24,74] :
    co=0
    for j in A :
        if j>=i :
            co+=1
    B.append(co)

#print(B)

print((B[0]-2)*B[1]*(B[1]-1)//2 + (B[1]-1)*B[2] + (B[0]-1)*B[3] + B[4])

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
def prime_decomposition(n, table):
    i = 2
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
table = []
for j in range(2,n+1):
  prime_decomposition(j, table)
c = Counter(table).values()
cc = Counter(c)
count_2 = cc[2] + cc[3]
count_4 = 0
for i in range(4,14):
  count_4+=cc[i]
count_14 = 0
for i in range(14,24):
  count_14+=cc[i]
count_24 = 0
for i in range(24,74):
  count_24+=cc[i]
count_74 = 0
for i in range(74,101):
  count_74+=cc[i]
count_24 += count_74
count_14 += count_24
count_4 += count_14
count_2 += count_4
print(count_74+count_24*max([0,count_2-1])+count_14*max(count_4-1,0)+max([count_2-2,0])*max([count_4-1,0])*count_4//2)

Submission status: Accepted

Solution code:
n = int(input())
# 素数判定
import math
def is_prime(num):
    if num < 2:
        return False
    if num == 2 or num == 3 or num == 5:
        return True
    if num % 2 == 0 or num % 3 == 0 or num % 5 == 0:
        return False

    # 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    num_sqrt = math.sqrt(num)
    while prime <= num_sqrt:
        if num % prime == 0:
            return False
        prime += step
        step = 6 - step

    return True
  
# 素数列挙
def make_prime_list(num):
    if num < 2:
        return []

    prime_list = []
    for prime in range(2, num + 1):
        if is_prime(prime):
            prime_list.append(prime)
    return prime_list
  
prime_list = make_prime_list(n)
pcount={}
for p in prime_list:
    pcount[p]=0
for nn in range(2,n+1):
    for p in prime_list:
        n=nn
        if n<p:
            break
        while n%p==0:
            n//=p
            pcount[p]+=1

mcount = {}
for m in [3,5,15,25,75]:
    mcount[m]=0
for i in pcount.values():
    for j in mcount:
        if i >= j - 1:
            mcount[j] += 1
            
print(mcount[75] + mcount[5]*(mcount[5]-1)//2*(mcount[3]-2) + (mcount[3]-1)*mcount[25] + mcount[15] * (mcount[5] - 1))

Submission status: Accepted

Solution code:
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]
c = [0 for i in range(0, len(p))]

for i in range(0, len(p)):
    m = 1
    pi = p[i]
    while pi <= n:
        c[i] += n // pi
        m += 1
        pi = p[i]**m
        
c74 = 0
c24 = 0
c14 = 0
c4 = 0
c2 = 0

for i in range(0, len(p)):
    if c[i] >= 2:
        c2 += 1
    if c[i] >= 4:
        c4 += 1
    if c[i] >= 14:
        c14 += 1
    if c[i] >= 24:
        c24 += 1
    if c[i] >= 74:
        c74 += 1

print(c74 + (c4 - c14) * c14 + c14 * (c14 - 1) + (c2 - c24) * c24 + c24 * (c24 - 1) + (c2 - c4) * c4 * (c4 - 1) // 2 + c4 * (c4 - 1) * (c4 - 2) // 2)

Submission status: Accepted

Solution code:
import math
import collections
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass
def count_counter(c,n):
    res = 0
    for i in c.values():
        if i >= n:
            res += 1
    return res
    
n = int(input())
factors, ans = [], 0
for i in range(2,n+1):
    factors = factors + prime_factor(i)
c = collections.Counter(sorted(factors))
ans += count_counter(c,74)
ans += (count_counter(c,24)*(count_counter(c,2)-1))
ans += (count_counter(c,14)*(count_counter(c,4)-1))
ans += ((count_counter(c,4)*(count_counter(c,4)-1)*(count_counter(c,2)-2))//2)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

def IsPrime(A):
    prime=[2]
    for a in range(3,A+1):
        for p in prime:
            if a%p==0:
                break
        else:
            prime.append(a)
    return prime


prime=IsPrime(N)
#print(prime)
pcount={}
for p in prime:
    pcount[p]=0
for nn in range(2,N+1):
    for p in prime:
        n=nn
        if n<p:
            break
        while n%p==0:
            n//=p
            pcount[p]+=1
#print(pcount)
mcount={}
for i in [75,25,15,5,3]:
    mcount[i]=0
for p in prime:
    for i in [75,25,15,5,3]:
        if pcount[p]>=i-1:
            mcount[i]+=1
#print(mcount)
print(mcount[75]+\
        mcount[25]*(mcount[3]-1)+\
        mcount[15]*(mcount[5]-1)+\
        mcount[5]*(mcount[5]-1)//2*(mcount[3]-2))
#75/25*3/15*5/5*5*3

Submission status: Accepted

Solution code:
N = int(input())

# 素因数分解
def factorization( n, e ):
    for i in range( 2, N+1 ):
        for j in range( 2, i+1 ):
            while i % j == 0:
                e[j] += 1
                i /= j

# e の要素のうち m-1 以上のものの個数
def num( m ):
    return len( list(filter(lambda x: x>= m-1, e)) )


e = [0]*(N+1)
factorization( N, e )
ans = num(75) + num(25)*(num(3)-1) + num(15)*(num(5)-1) \
      + num(5)*(num(5)-1)*(num(3)-2)//2
print( ans )

Submission status: Accepted

Solution code:
n=int(input())
C=[0]*(n+1)
for i in range(2,n+1):
    tmp=i
    for j in range(2,i+1):
        while tmp%j==0:
            C[j]+=1
            tmp//=j
def num(n):
    return len(list(filter(lambda x:x>=n-1,C)))
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:
def add_divisors(n, divisors):
    primes = [
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
        43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
    ]
    for prime in primes:
        while True:
            if n % prime == 0:
                if prime in divisors.keys():
                    divisors[prime] += 1
                else:
                    divisors[prime] = 1
                n /= prime
            else:
                break

divisors = {}
n = int(input())
for i in range(1,n+1):
    add_divisors(i, divisors)

c74_ = 0

c24_ = 0
c2_23 = 0

c14_ = 0
c4_13 = 0

c4_ = 0
c2_3 = 0

for k in divisors.keys():
    if divisors[k] >= 74:
        c74_ += 1

    if divisors[k] >= 24:
        c24_ += 1
    elif divisors[k] >= 2:
        c2_23 += 1

    if divisors[k] >= 14:
        c14_ += 1
    elif divisors[k] >= 4:
        c4_13 += 1

    if divisors[k] >= 4:
        c4_ += 1
    elif divisors[k] >= 2:
        c2_3 += 1

ans = 0

# 75
if c74_ >= 1:
    ans += c74_

# 3*25
if c24_ >= 2:
    ans += c24_ * (c24_ - 1)
if c2_23 >= 1 and c24_ >= 1:
    ans += c2_23 * c24_

# 5*15
if c14_ >= 2:
    ans += c14_ * (c14_ - 1)
if c4_13 >= 1 and c14_ >= 1:
    ans += c4_13 * c14_

# 3*5*5
if c4_ >= 3:
    ans += c4_ * (c4_ - 1) * (c4_ - 2) // 2
if c2_3 >= 1 and c4_ >= 2:
    ans += c2_3 * c4_ * (c4_ - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
n = int(input())

#cnt for every appearance of each prime number
primelist = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
cntlist = [0]*50
res = 0

for num in range(2,n+1):
    for prime in primelist:
        while(num%prime==0):
            num //= prime
            cntlist[prime] += 1

nonZeroPrime = [prime for prime in primelist if cntlist[prime]!=0]

#print(nonZeroPrime)
#print(cntlist)

#(3,5,5) (2,4,4)
perm = list(combinations(nonZeroPrime,3))
for t in perm:
    nonZeroCnt = [cntlist[prime] for prime in t]
    nonZeroCnt.sort()
    if(nonZeroCnt[0]>1 and nonZeroCnt[1]>3 and nonZeroCnt[2]>3):
        res+=1
    if(nonZeroCnt[0]>=4):
        res+=2

tuples = []
#(5,15) (4,14)
perm = list(combinations(nonZeroPrime,2))
for t in perm:
    nonZeroCnt = [cntlist[prime] for prime in t]
    nonZeroCnt.sort()
    nonZeroCnt = tuple(nonZeroCnt)
    if(nonZeroCnt[0]>=4 and nonZeroCnt[1]>=14):
        res += 1
    if(nonZeroCnt[0]>=14):
        res += 1

#(3,25) (2,24)
for t in perm:
    nonZeroCnt = [cntlist[prime] for prime in t]
    nonZeroCnt.sort()
    nonZeroCnt = tuple(nonZeroCnt)
    if(nonZeroCnt[0]>=2 and nonZeroCnt[1]>=24):
        res += 1
    if(nonZeroCnt[0]>=24):
        res += 1

#(75)

res += len([cnt for cnt in cntlist if cnt>=74])
print(res)

Submission status: Accepted

Solution code:
from itertools import combinations

N = int(input())
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]


def count(p, N, n=1):
    if p**n > N:
        return 0
    return N//(p**n) + count(p, N, n+1)


n_prime = [count(p, N) for p in prime]

ret = 0

## 5 x 5 x 3 = 75
gt4 = [n for n in n_prime if n >= 4]
gt2 = [n for n in n_prime if n >= 2]
ret += len(list(combinations(gt4, 2))) * (len(gt2)-2)

## 15 x 5 = 75
gt14 = [n for n in n_prime if n >= 14]
gt4 = [n for n in n_prime if n >= 4]
ret += len(gt14) * (len(gt4)-1)

## 25 x 3 = 75
gt24 = [n for n in n_prime if n >= 24]
gt2 = [n for n in n_prime if n >= 2]
ret += len(gt24) * (len(gt2)-1)

## 75 = 75
gt74 = [n for n in n_prime if n >= 74]
ret += len(gt74)

print(ret)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [long(input_raw[0])]
    prim_dict = {}

    for i in range(2, N + 1):
        p = 2
        X = i
        for p in range(2, i + 1):
            while X % p == 0:
                if p not in prim_dict:
                    prim_dict[p] = 2
                else:
                    prim_dict[p] += 1
                X /= p
    count_3over = 0
    count_5over = 0
    count_15over = 0
    count_25over = 0
    count_75over = 0
    for p in prim_dict:
        if prim_dict[p] >= 75:
            count_75over += 1L
        if prim_dict[p] >= 25:
            count_25over += 1L
        if prim_dict[p] >= 15:
            count_15over += 1L
        if prim_dict[p] >= 5:
            count_5over += 1L
        if prim_dict[p] >= 3:
            count_3over += 1L

    count = 0L
    #3,3,5
    count += (count_5over * (count_5over-1))/2 * (count_3over - 2)
    count += count_15over * (count_5over - 1)
    count += count_25over * (count_3over - 1)
    count += count_75over
    print count


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


def calc_divisors_of_factorial(n):
    ret = defaultdict(int)
    for i in range(1, n+1):
        divisors = calc_prime_divisors(i)
        for d in divisors:
            ret[d] += divisors[d]
    return ret


def calc_prime_divisors(n):  # do not contain 1
    ret = defaultdict(int)
    for i in range(2, n+1):
        if is_prime(i):
            while n % i == 0:
                n = n // i
                ret[i] += 1
            if n == 1:
                break
    return ret


def is_prime(n):
    memo = {}
    def calc(n):
        if n in memo:
            return memo[n]
        if n == 1 or n == 2:
            return True
        if n % 2 == 0:
            return False
        d = 3
        while True:
            if d**2 > n:
                break
            if n % d == 0:
                memo[n] = False
                return False
            d += 2
        memo[n] = True
        return True
    return calc(n)


def get_over(divisors, n):
    ret = 0
    for d in divisors:
        if divisors[d]+1 >= n:
            ret += 1
    return ret


def factorial(n):
    memo = {}
    def calc(n):
        if n in memo:
            return memo[n]
        if n <= 1:
            return 1
        ret = n *factorial(n-1)
        memo[n] = ret
        return ret
    return calc(n)


def combination(n, k):
    if n <= 0:
        return 0
    return factorial(n) // (factorial(k) * factorial(n-k))


def solve(n):
    prime_divisors = calc_divisors_of_factorial(n)
    ret = 0
    over_75 = get_over(prime_divisors, 75)
    over_25 = get_over(prime_divisors, 25)
    over_15 = get_over(prime_divisors, 15)
    over_5 = get_over(prime_divisors, 5)
    over_3 = get_over(prime_divisors, 3)

    if over_75 > 0:
        ret += combination(over_75, 1)
    if over_25 > 0 and over_3-1 > 0:
        ret += combination(over_25, 1) * combination(over_3 - 1, 1)
    if over_15 > 0 and over_5-1 > 0:
        ret += combination(over_15, 1) * combination(over_5 - 1, 1)
    if over_5 > 0 and over_3-2>0:
        ret += combination(over_5, 2) * combination(over_3 - 2, 1)

    return ret


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
e = [0 for i in range(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:
# -*- coding: utf-8 -*-

N = int(input())

pf = [0] * (N + 1)  # Prime factors

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


def count(n):
    f = filter(lambda x: x >= n - 1, pf)
    return len(list(f))


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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())

#素因数分解
def factorize(n):
    fct=[]
    b,e=2,0
    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

import math

l=factorize(math.factorial(n))

a74=0
a24=0
a14=0
a4=0
a2=0

for i,j in l:
    if int(j)>=74:
        a74+=1
        a24+=1
        a14+=1
        a4+=1
        a2+=1
    elif int(j)>=24:
        a2+=1
        a24+=1
        a14+=1
        a4+=1
    elif int(j)>=14:
        a2+=1
        a4+=1
        a14+=1
    elif int(j)>=4:
        a2+=1
        a4+=1
    elif int(j)>=2:
        a2+=1


if a74+a24*(a2-1)+a14*(a4-1)+a4*a4*0.5*(a2-2)>=0:
    print(int(a74+a24*(a2-1)+a14*(a4-1)+a4*(a4-1)*0.5*(a2-2)))
else:
    print(0)

Submission status: Accepted

Solution code:
import sys

def get_pfn(N):
  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
  return e


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

def main():
  input = sys.stdin.readline
  N = int(input())
  e = get_pfn(N)
  print(num(75, e) +\
        num(25, e) * (num(3, e) - 1) +\
        num(15, e) * (num(5, e) - 1) +\
        num(5, e) * (num(5, e) - 1) * (num(3, e) - 2) // 2)

  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
N = int(input())

counter = [0] * (N + 1)

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

def num(n):
    return len([m for m in range(2, N + 1) if counter[m] >= n - 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:
import math

def combinations_count(n, r):
    if n <= 0 or n-r < 0:
      return 0
    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]
  
N = int(input())
primes = primes(N)
num = [0] * 5

for prime in primes:
  cnt = 0
  x = N
  while x >= prime:
    x = int(x/prime)
    cnt += x
  if cnt >= 74:
    num[0] += 1
  if cnt >= 24:
    num[1] += 1
  if cnt >= 14:
    num[2] += 1
  if cnt >= 4:
    num[3] += 1
  if cnt >= 2:
    num[4] += 1

ans = num[0] + num[1] * (num[4] - 1) + num[2] * (num[3] - 1) + \
combinations_count(num[3], 2) * (num[4] - 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
import random
class Prime:
    seed_primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
    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_brute_force(n)
        return self.is_prime_miller_rabin(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_brute_force(self,n):
        for k in range(2,int(math.sqrt(n))+1):
            if n%k==0:return False
        return True
    def is_prime_miller_rabin(self,n):
        d=n-1
        while d&1==0:d>>=1
        witnesses=self.get_witnesses(n)
        for w in witnesses:
            y=pow(w,d,n)
            while d!=n-1and y!=1and y!=n-1:
                y=y*y%n
                d<<=1
            if y!=n-1and d&1==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<3825123056546413051:return 9
            return 12
        return self.seed_primes[:_get_range(num)]
    def gcd(self,a,b):
        if a<b:return self.gcd(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
*d,=sorted(Prime().find_factors(math.factorial(int(input()))).values())
a=0
n=len(d)
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            a+=3*(d[i]>3)or d[i]>1and d[j]>3and d[k]>3
        a+=(2*(d[i]>13)or d[i]>3and d[j]>13)+(2*(d[i]>23)or d[i]>1and d[j]>23)
    a+=d[i]>73
print(a)

Submission status: Accepted

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

from itertools import combinations
from functools import reduce
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]

def prime_factorization(x):
  # 100までの素数でしか動かない
  facters = []

  if x == 1:
    return [1]

  if x in primes:
    return [x]

  for p in primes:
    while x%p == 0:
      x /= p
      facters += [p]
  return facters


facters = {i:prime_factorization(i) for i in range(1, 100+1)}

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

  nn = []
  for i in range(2, n+1):
    nn += facters[i]
  nn = [x+1 for x in Counter(nn).values()]
  count_5 = 0
  count_3 = 0
  count_15 = 0
  count_25 = 0
  count_75 = 0
  f = lambda x: x*f(x-1) if x>1 else 1
  comb = lambda x,y: int(f(x) / (f(y)*f(x-y))) if y<=x else 0
  for x in nn:
    if 75 <= x:
      count_75 += 1
    if 25 <= x:
      count_25 += 1
    if 15 <= x:
      count_15 += 1
    if 5 <= x:
      count_5 += 1
    if 3 <= x:
      count_3 += 1

  counts = [count_3, count_5, count_15, count_25, count_75] # length: 5

  ans = comb(count_5, 2) * (count_3 - 2) \
      + count_15 * (count_5 - 1) \
      + count_25 * (count_3 - 1) \
      + count_75
  print(ans)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
#組み合わせ、コンビネーション
def cmb(n,r):
    if n==0:return 0
    else:
        r=min(r,n-r)
        result=1
        for i in range(n-r+1,n+1):
            result*=i
        for i in range(1,r+1):
            result//=i
        return result

#素因数分解、辞書を返す
def factorize(n):
    i=2
    result={}
    while True:
        if i**2>n:
            break
        count=0
        while n%i==0:
            n//=i
            count+= 1
        if count!=0:
            result[i]=count
        i+=1
    if n>1:
        result[n]=1
    return result

N = int(input())
l={}
for i in range(1,N+1):
    for i,j in factorize(i).items():
        l[i] = l.get(i,0)+j


l2 = [0]*5

r = 0
for j,i in l.items():
    if i>=74:
        l2[4]+=1
    elif i>=24:
        l2[3]+=1
    elif i>=14:
        l2[2]+=1
    elif i>=4:
        l2[1]+=1
    elif i>=2:
        l2[0]+=1

r += l2[4]
r += sum(l2[3:])*(sum(l2)-1)
r += sum(l2[2:])*(sum(l2[1:])-1)
r += cmb(sum(l2[1:]),2)*(sum(l2)-2)
print(r)

Submission status: Accepted

Solution code:
N = int(input())
p = [
    sum(N // (i**k) for k in range(1, 8))
    for i in range(2, 97 + 1)
    if all(i % j != 0 for j in range(2, i))
]
def f(m):
  return len([i for i in p if i >= m])
ans = f(74) + f(24) * (f(2) - 1) + f(14) * (f(4) - 1) + f(4) * (f(4) - 1) * (f(2) - 2) // 2
print(ans)

Submission status: Accepted

Solution code:
def prime_decomposition(n):
    p = 2
    prime = {}
    while n!=1:
        while n%p == 0:
            n = n/p
            if p not in prime:
                prime[p] = 0
            prime[p] += 1
        p += 1
    return prime

N = int(input())
primes = {}
for i in range(1,N+1):
    # print('now prime_decomposition',i)
    i_prime = prime_decomposition(i)
    for p in i_prime:
        if p not in primes:
            primes[p] = 0
        primes[p] += i_prime[p]

over75 = 0
over25 = 0
over15 = 0
over5 = 0
over3 = 0
for p in primes:
    # print('now primes',p)
    if primes[p]>=74:
        over75 += 1
    if primes[p]>=24:
        over25 += 1
    if primes[p]>=14:
        over15 += 1
    if primes[p]>=4:
        over5 += 1
    if primes[p]>=2:
        over3 += 1

ans75 = over75
ans253 = over25*(over3-1)
ans155 = over15*(over5-1)
ans553 = over5*(over5-1)/2*(over3-2)

ans = ans75+ans253+ans155+ans553

print(int(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:
# 75=3*5*5
# N=a^2*b^4*c^4 | a^14+b^4 | a^24*b^2 | a^74
n=int(input())

cntDiviser=[0 for _ in range(n+1)]
for i in range(2,n+1):
    tmp=i
    for j in range(2,i+1):
        while tmp%j==0:
            cntDiviser[j]+=1
            tmp//=j # //整数の商

def num(m):
    return len(list(filter(lambda x:x>=m,cntDiviser)))

print(
    num(74)
    +num(24)*(num(2)-1)
    +num(14)*(num(4)-1)
    +num(4)*(num(4)-1)*(num(2)-2)//2 # 4,4,2の組み合わせの数
    )

Submission status: Accepted

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


def num(m):
    #lのvalueがm-1以上のものを返す
    return len(list(filter(lambda x:x>=m-1, l)))


print(num(75) + num(25)*(num(3)-1) + num(15)*(num(5)-1)
 + num(5)*(num(5)-1)*(num(3)-2)//2#num(5)の入れ替えに関して2!で割る
 )

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 = 101
prime = [True]*(N+1)
count = [0]*(N+1)
prime[0] = prime[1] = False

for i in range(N+1):
    if prime[i]:
        for j in range(2*i, N+1, i):
            prime[j] = False
a = int(input())
for i in range(1,a+1):
    cur = i
    for j in range(2,i+1):
        if prime[j]: 
            while cur%j==0:
                count[j]+=1
                cur//=j
            
s=r=0
for i in range(1,a+1):
    if count[i]>=4:
        s+=1
        r+=1
    elif count[i]>=2:r+=1
def num(m): # e の要素のうち m-1 以上のものの個数
    return len(list(filter(lambda x: x >= m-1, count)))

#if s>=2and r-2>=1:print(combinations_count(s,2)*(r-2))
#else:print(0)
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:
def isprime(n):
    if(n<2):
        return False
    for i in range(2,n):
        if(n%i==0):
            return False
    return True

def primelist(n):
    return [i for i in range(n) if isprime(i)]

def factor(n):
    f = {}
    while(n > 1):
        for p in primelist(n+1):
            if(n % p == 0):
                f[p] = f.get(p, 0) + 1
                n //= p
    return f

def factorfactorial(n):
    f = {}
    for i in range(1,n+1):
        fi = factor(i)
        for k, v in fi.items():
            f[k] = f.get(k,0) + v
    return f

# 75 = 3*5*5 = 3*25 = 5*15 
n = int(input())
f = factorfactorial(n)

# print(f)
cnt = 0

for i in f.keys():
    if(f[i]>=75-1):
        cnt += 1
    for j in primelist(n+1):
        if(i==j):
            continue
        if(f[i]>=25-1 and f[j]>=3-1):
            cnt += 1
        if(f[i]>=15-1 and f[j]>=5-1):
            cnt += 1
        if(i > j):
            for k in primelist(n+1):
                if k in [i,j]:
                    continue
                if(f[i]>=5-1 and f[j]>=5-1 and f[k]>=3-1):
                    cnt += 1



print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
c = Counter()
for n in range(2, N + 1):
    i = 2
    while i**2 <= n:
        count = 0
        while n % i == 0:
            n //= i
            count += 1
        if count != 0:
            c[i] += count
        i += 1
    if n > 1:
        c[n] += 1


def num(m):  # 指数がm-1以上の素因数の個数を求める
    return len(list(filter(lambda x: x >= m - 1, c.values())))


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

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
c = Counter()
for n in range(2, N + 1):
    i = 2
    while i**2 <= n:
        count = 0
        while n % i == 0:
            n //= i
            count += 1
        if count != 0:
            c[i] += count
        i += 1
    if n > 1:
        c[n] += 1

d = Counter()
for v in c.values():
    if 2 <= v:
        d["3"] += 1
    if 4 <= v:
        d["5"] += 1
    if 14 <= v:
        d["15"] += 1
    if 24 <= v:
        d["25"] += 1
    if 74 <= v:
        d["75"] += 1

ans = 0
ans += d["75"]
ans += (d["5"] - 1) * d["15"]
ans += (d["3"] - 1) * d["25"]
ans += (d["3"] - 2) * d["5"] * (d["5"] - 1) // 2
print(ans)