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:
n = int(input())
hurui = [1]*(n+1)
hurui[0] = 0
hurui[1] = 0
sq = int(n**(1/2))+3

for i in range(2,sq):
    for j in range(2,n//i+1):
        hurui[j*i] = 0
p = []

for i in range(n+1):
    if hurui[i]:
        p.append(i)

cnt = {pi:0 for pi in p}

for pi in p:
    tmp = n
    while tmp>0:
        tmp //= pi
        cnt[pi] += tmp
      
cnt2 = {2:0, 4:0, 14:0, 24:0,74:0}

for key in cnt:
    if cnt[key] >= 2:
        cnt2[2]+=1
    if cnt[key] >= 4:
        cnt2[4]+=1
    if cnt[key] >= 14:
        cnt2[14]+=1
    if cnt[key] >= 24:
        cnt2[24]+=1
    if cnt[key] >= 74:
        cnt2[74]+=1

ans = 0

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

Submission status: Accepted

Solution code:
"""
22:17:30

"""

from collections import defaultdict
N = int(input())


def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

def factorization(N):
    factors = defaultdict(int)
    for n in range(1,N+1):
        if n <= 3:
            factors[n] += 1
            continue
        primes = getprime(int(n**0.5))
        for prime in primes:
            while n % prime == 0:
                factors[prime] += 1
                n //= prime
                # print(factors,n)
        if n != 1:
            factors[n] += 1
    return factors

d = factorization(N)
# 5種類の数字を洗い出す
n_74 = 0
n_24 = 0
n_14 = 0
n_4 = 0
n_2 = 0
for k in d.keys():
    n = d[k]
    if n >= 2:
        n_2 += 1
    if n >= 4:
        n_4 += 1
    if n >= 14:
        n_14 += 1
    if n >= 24:
        n_24 += 1
    if n >= 74:
        n_74 += 1
# print(n_2,n_4,n_14,n_24,n_74)
cnt = 0
# 1,1,74
cnt += n_74
# 1,3,25
cnt += (n_2-1) * n_24
# 1,5,15
cnt += (n_4-1) * n_14
# 3,5,5
cnt += (n_2-2) * (n_4)*(n_4-1)//2
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict


n = int(input())
div = defaultdict(int)

for i in range(2, n+1):
    num = i
    while num != 1:
        for d in range(2, num+1):
            if num % d == 0:
                num //= d
                div[d] += 1
                break
            else:
                continue

values = list(div.values())
over2 = 0
over4 = 0
over14 = 0
over24 = 0
over74 = 0
for value in values:
    if value >= 2:
        over2 += 1
    if value >= 4:
        over4 += 1
    if value >= 14:
        over14 += 1
    if value >= 24:
        over24 += 1
    if value >= 74:
        over74 += 1

ans1 = max(0, over4 * (over4-1) * (over2-2) // 2)
ans2 = max(0, over14 * (over4-1))
ans3 = max(0, over24 * (over2-1))
ans4 = over74
res = sum([ans1, ans2, ans3, ans4])
print(res)

Submission status: Accepted

Solution code:
n = int(input())
primeL = []
for i in range(2,n+1):
    key = 0
    for j in primeL:
        if i % j == 0:
            key = 1
    if key == 0:
        primeL.append(i)
l = []
for i in primeL:
    count = 0
    a = i
    while a <= n:
        count += n//a
        a *= i
    l.append(count)
p = 0
q = 0
r = 0
s = 0
t = 0
for i in range(len(l)):
    if l[i] >= 74:
        p += 1
    if l[i] >= 24:
        q += 1
    if l[i] >= 14:
        r += 1
    if l[i] >= 4:
        s += 1
    if l[i] >= 2:
        t += 1
ans = 0
ans += p
ans += q*(t-1)
ans += r*(s-1)
ans += s*(s-1)*(t-2)//2
print(ans)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
prm = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
abc = list(itertools.permutations(prm,3))
ab  = list(itertools.permutations(prm,2))
ans = 0
for i in abc:
    a=0; b=0; c=0
    A=i[0]; B=i[1]; C=i[2]
    while A<=N:
        a += N//A
        A *= i[0]
    while B<=N:
        b += N//B
        B *= i[1]
    while C<=N:
        c += N//C
        C *= i[2]
    if a>=4 and b>=4 and c>=2:
        ans += 1
ans //= 2
for i in ab:
    a=0; b=0
    A=i[0]; B=i[1]
    while A<=N:
        a += N//A
        A *= i[0]
    while B<=N:
        b += N//B
        B *= i[1]
    if a>=14 and b>=4:
        ans += 1
    if a>=24 and b>=2:
        ans += 1
for i in prm:
    a=0; A=i
    while A<=N:
        a += N//A
        A *= i
    if a>=74:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
d = defaultdict(int)

for i in range(1,n+1):
    prime = prime_factorize(i)
    for p in prime:
        d[p] += 1

#5*5*3
#15*5
#25*3
#75

over4 = 0
over2 = 0
over14 = 0
over24 = 0
over74 = 0
for dd in d.values():
    if dd >= 4:
        over4 += 1
    if dd >= 2:
        over2 += 1
    if dd >= 14:
        over14 += 1
    if dd >= 24:
        over24 += 1
    if dd >= 74:
        over74 += 1

i1 = over74
i2 = over24 * (over2 - 1)
i3 = over14 * (over4 - 1)
i4 = over4 * (over4 - 1) * (over2-2) // 2
print(i1+i2+i3+i4)

Submission status: Accepted

Solution code:
n=int(input())
primelist=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
ll=[0,0,0,0,0]
for i in range(len(primelist)):
  a=primelist[i]
  t=n
  po=0
  while(t>0):
    t=int(t/a)
    po+=t
  if(po>=74):
    ll[4]+=1
  if(po>=24):
    ll[3]+=1
  if(po>=14):
    ll[2]+=1
  if(po>=4):
    ll[1]+=1
  if(po>=2):
    ll[0]+=1
ans=ll[4]+(ll[3])*(ll[0]-1)+(ll[2])*(ll[1]-1)+(ll[1])*(ll[1]-1)*(ll[0]-2)/2
print(int(ans))

Submission status: Accepted

Solution code:
n=int(input())
c=[0]*(n+1)
for i in range(2,n+1):
  num=i
  for j in range(2,i+1):
    while num%j==0:
      c[j]+=1
      num //= j
def cnt(x):
  count=0
  for i in range(n+1):
    if c[i]>=x-1:count+=1
  return count
      
print(cnt(75)+cnt(25)*(cnt(3)-1)+cnt(15)*(cnt(5)-1)+cnt(5)*(cnt(5)-1)*(cnt(3)-2) //2)

Submission status: Accepted

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
fact = [0]*(N+1)
for i in range(2, N+1):
    tmp = i
    for j in range(2, i+1):
        while tmp % j == 0:
            fact[j] += 1
            tmp //= j


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

ans = 0
ans += num(75) + 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())
P=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
c=0
for i in range(15):
  a=n
  b=0
  while a>=P[i]:
    a=a//P[i]
    b=b+a
  if b>=74:
    c=c+1
for i in range(15):
  a=n
  b=0
  while a>=P[i]:
    a=a//P[i]
    b=b+a
  if b>=24:
    d=0
    for j in range(15):
      if j==i:
        continue
      a=n
      b=0
      while a>=P[j]:
        a=a//P[j]
        b=b+a
      if b>=2:
        c=c+1
for i in range(15):
  a=n
  b=0
  while a>=P[i]:
    a=a//P[i]
    b=b+a
  if b>=14:
    d=0
    for j in range(15):
      if j==i:
        continue
      a=n
      b=0
      while a>=P[j]:
        a=a//P[j]
        b=b+a
      if b>=4:
        c=c+1
for i in range(15):
  a=n
  b=0
  while a>=P[i]:
    a=a//P[i]
    b=b+a
  if b>=4:
    d=0
    for j in range(i+1,15):
      if j==i:
        continue
      a=n
      b=0
      while a>=P[j]:
        a=a//P[j]
        b=b+a
      if b>=4:
        d=0
        for k in range(15):
          if k==i or k==j:
            continue
          a=n
          b=0
          while a>=P[k]:
            a=a//P[k]
            b=b+a
          if b>=2:
            c=c+1
print(c)

Submission status: Accepted

Solution code:
n=int(input())
if n<=9:
    print(0)
    exit()
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
ans=[]
l=[]
for i in range(2,n+1):
    c=factorization(i)
    for j in c:
        if not j[0] in l:
            l.append(j[0])
            ans.append(j[1])
        else:
            ans[l.index(j[0])]+=j[1]
kai=0
k24=0
k2=0
k14=0
k4=0
for i in ans:
    if i>=74:
        kai+=1
    if i>=24:
        k24+=1
    if i>=2:
        k2+=1
    if i>=14:
        k14+=1
    if i>=4:
        k4+=1
print(kai+k24*(k2-1)+k14*(k4-1)+(k2-2)*k4*(k4-1)//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)))

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

Submission status: Accepted

Solution code:
# D - 756
# 75 = 3*5*5なので、(4個以上ある素因数のうち2つを選ぶ組合せ)×(残りから2個以上ある素因数1つを選ぶ組合せ) が解の一部
# 15*5, 25*3, 75についても同様

import collections, math

N = int(input())

# n以下の全ての素数のセットを返す関数
def prime_set(n):
    primes = set(range(2, n+1))
    for i in range(2, int(n**0.5) + 1):
        primes.difference_update(range(i*2, n+1, i))
    return primes

# nを素因数分解して素因数の全リストを返す関数
def prime_factors_duplicating_list(n):
    f = []
    for i in prime_set(int(n**0.5) + 1):
        while n % i == 0:
            f.append(i)
            n //= i
    if n > 1:
        f.append(n)
    return f

def comb(n, r):
    if n < r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N_factorial_prime_factors = []
for i in range(1, N+1):
    N_factorial_prime_factors.extend(prime_factors_duplicating_list(i))

N_factorial_prime_factors = collections.Counter(N_factorial_prime_factors)

n_74plus_factors = set()
n_24plus_factors = set()
n_14plus_factors = set()
n_4plus_factors = set()
n_2plus_factors = set()

for key in N_factorial_prime_factors:
    for border in [2,4,14,24,74]:
        if N_factorial_prime_factors[key] >= border:
            eval("n_" + str(border) + "plus_factors.add(key)")

ans = 0
ans += comb(len(n_4plus_factors), 2) * (len(n_4plus_factors) - 2 + len(n_2plus_factors - n_4plus_factors)) # 3*5*5
ans += len(n_14plus_factors) * (len(n_14plus_factors) - 1 + len(n_4plus_factors - n_14plus_factors)) # 15*5
ans += len(n_24plus_factors) * (len(n_24plus_factors) - 1 + len(n_2plus_factors - n_24plus_factors)) # 25*3
ans += len(n_74plus_factors) # 75

print(ans)

Submission status: Accepted

Solution code:
N = int(input())


def fac(n):
    att = []
    t = n
    for i in range(2, int(-(-n ** 0.5 // 1) + 1)):
        while (t % i == 0):
            t //= i
            att += [i]
    if t > 1:
        att += [t]
    return att


def lnum(m):
    return len(list(filter(lambda x: memo[x] >= m - 1, memo)))


memo = {}
for i in range(2, N + 1):
    fl = fac(i)
    for f in fl:
        if f in memo:
            memo[f] += 1
        else:
            memo[f] = 1
s = []
for m in memo:
    if memo[m] == 1:
        continue
    s += [memo[m] + 1]
ans = lnum(75) + lnum(25) * (lnum(3) - 1) + lnum(15) * (lnum(5) - 1) \
    + lnum(5) * (lnum(5) - 1) // 2 * (lnum(3) - 2)
print(ans)

Submission status: Accepted

Solution code:
import os, sys, re, math

N = int(input())

factor = {}

def doit(n):
    ret = {}
    for i in range(2,11):
        while n % i == 0:
            n = n // i
            ret[i] = ret.get(i,0) + 1

    if n != 1:
        ret[n] = ret.get(n,0) + 1
    return ret

for i in range(2,N+1):
    tmp = doit(i)
    for k,v in tmp.items():
        factor[k] = factor.get(k,0) + v

d3 = 0
d5 = 0
d15 = 0
d25 = 0
d75 = 0

for k,v in factor.items():
    if v >= 74:
        d75 += 1
    if v >= 24:
        d25 += 1
    if v >= 14:
        d15 += 1
    if v >= 4:
        d5 += 1
    if v >= 2:
        d3 += 1

print(d75+d25*(d3-1)+d15*(d5-1)+d5*(d5-1)*(d3-2)//2)

Submission status: Accepted

Solution code:
n = int(input())
p = {}
for i in range(2, n + 1):
    j = i
    for d in range(2, j + 1):
        while j % d == 0:
            p[d] = p.get(d, 0) + 1
            j //= d

def doit(ds, ps):
    if ds == []:
        return 1
    if ps == []:
        return 0
    ret = doit(ds, ps[1:])
    if ps[0] + 1 >= ds[0]:
        ret += doit(ds[1:], ps[1:])
    return ret

ret = 0
for ds in ([3, 5, 5], [5, 3, 5], [5, 5, 3], [5, 15], [15, 5], [3, 25], [25, 3], [75]):
    ret += doit(ds, list(p.values()))
print(ret)

Submission status: Accepted

Solution code:
n = int(input())
f = [0]*(n+1)
for i in range(2,n+1):
    a = i
    for j in range(2,i+1):
        while a % j == 0:
            f[j] += 1
            a //= j
def number(m):
    c = 0
    for i in range(n):
        if f[i] >= m - 1:
            c += 1
    return c
print(number(75) + number(25)*(number(3) - 1) + number(15)*(number(5) - 1) 
+ number(5)*(number(5) - 1)*(number(3) - 2)//2)

Submission status: Accepted

Solution code:
import math
N = int(input())
e = [0] * (N+1)

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

import collections

for i in range(2,N+1):
  c = collections.Counter(prime_factorize(i))
  for key,value in c.items():
    e[key] += value
#print(e)

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:
def prime_factor(n):
    p = {}
    for i in range(2,n):
        if n % i == 0:
            p[i] = 0
        while n % i == 0:
            n //= i
            p[i] += 1
        if i * i > n: break
    if n != 1:
        p[n] = 1
    return p

N = int(input())
if N == 1:
    print(0)
else:
    
    pN = {}
    for i in range(2,N+1):
        p = prime_factor(i)
        for x in p:
            if x not in pN:
                pN[x] = p[x]
            else:
                pN[x] += p[x]
    
    # 75 = 3 * 5 * 5
    res = 0
    for x in pN:
        for y in pN:
            for z in pN:
                if (x < y and y < z):
                    if(pN[x]>=2 and pN[y]>=4 and pN[z]>=4):
                        res+=1
                    if(pN[x]>=4 and pN[y]>=2 and pN[z]>=4):
                        res+=1
                    if(pN[x]>=4 and pN[y]>=4 and pN[z]>=2):
                        res+=1
    
    # 75 = 3 * 25
    for x in pN:
        for y in pN:
            if x < y:
                if(pN[x]>=24 and pN[y]>= 2):
                    res+=1
                if(pN[x]>= 2 and pN[y]>=24):
                    res+=1
    
    # 75 = 15 * 5
    for x in pN:
        for y in pN:
            if x < y:
                if(pN[x]>=14 and pN[y]>= 4):
                    res+=1
                if(pN[x]>= 4 and pN[y]>=14):
                    res+=1
    
    if pN[2] >= 74:
        res += 1
        
    print(res)

Submission status: Accepted

Solution code:
# 素因数分解(o√N)
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


n = int(input())
d = {}
for i in range(1, n+1):
    for j in prime_factorize(i):
        if j not in d:
            d[j] = 1
        else:
            d[j] += 1
l = d.values()

ans = 0

 # (3,5,5)その１
a = 0
b = 0
for i in l:
    if 2 <= i <= 3:
        a += 1
for j in l:
    if 4 <= j:
        b += 1
ans += a*b*(b-1)/2

# (3,5,5)その２
a = 0
b = 0
for i in l:
    if 4 <= i:
        a += 1
ans += a*(a-1)*(a-2)/2

#(5,15)その１
a = 0
b = 0
for i in l:
    if 4 <= i <= 13:
        a += 1
for j in l:
    if 14 <= j:
        b += 1
ans += a*b

#(5,15)その２
a = 0
b = 0
for i in l:
    if 14 <= i:
        a += 1
ans += a*(a-1)

#(3,25)その１
a = 0
b = 0
for i in l:
    if 2 <= i <= 23:
        a += 1
for j in l:
    if 24 <= j:
        b += 1
ans += a*b

# (3,25)その２
a = 0
b = 0
for i in l:
    if 24 <= i:
        a += 1
ans += a*(a-1)

# (75)
a = 0
b = 0
for i in l:
    if 74 <= i:
        a += 1
ans += a

print(int(ans))

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())


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


divisors = []
for i in range(2, N + 1):
    divisors.extend(prime_factorize(i))

e = Counter(divisors)
e_list = [e[i] for i in e.keys() if i != 1]


def num(x):
    return len([i for i in e_list if i >= x])


l2 = num(2)
l4 = num(4)
answer = num(74) + \
         num(24) * (l2 - 1) + \
         num(14) * (l4 - 1) + \
         l4 * (l4 - 1) * max(0, (l2 - 2)) // 2
print(answer)

Submission status: Accepted

Solution code:
N = int(input())

prime_list = [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:
            prime_list[j] += 1
            cur //= j
            
def num(m):
    return len(list(filter(lambda x: x >= m-1, prime_list)))

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:
answer = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 8, 8, 11, 11, 11, 11, 14, 14, 32, 32, 35, 35, 35, 35, 42, 42, 42, 42, 49, 49, 49, 49, 49, 49, 75, 75, 86, 86, 86, 86, 86, 86, 123, 123, 131, 131, 131, 131, 148, 148, 153, 153, 170, 170, 170, 170, 170, 170, 227, 227, 227, 227, 227, 227, 250, 250, 323, 323, 324, 324, 324, 324, 354, 354, 354, 354, 384, 384, 384, 384, 384, 391, 491, 491, 529, 529, 529, 529, 529, 529, 543]
N = int(input())
print(answer[N])

Submission status: Accepted

Solution code:
def slove():
    import sys
    import collections
    input = sys.stdin.readline

    n = int(input().rstrip('\n'))
    ls = []

    for i in range(1, n + 1):
        t = i
        for j in range(2, int(t ** 0.5) + 1):
            while True:
                if t % j == 0:
                    t //= j
                    ls.append(j)
                else:
                    break
        if t > 1:
            ls.append(t)

    ls = collections.Counter(ls)
    ls2 = []

    for k, v in ls.items():
        if v >= 74:
            ls2.append(75)
        if v >= 24:
            ls2.append(25)
        if v >= 14:
            ls2.append(15)
        if v >= 4:
            ls2.append(5)
        if v >= 2:
            ls2.append(3)

    ls2 = collections.Counter(ls2)
    cnt = 0
    cnt += (ls2[75])
    cnt += (ls2[25] * max(ls2[3]-1, 0))
    cnt += (ls2[15] * max(ls2[5]-1, 0))
    cnt += (ls2[5] * max(ls2[5]-1, 0) * max(ls2[3]-2, 0) // 2)
    print(cnt)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
n = int(input())

e = [0] * 101

for x in range(2, n + 1):
    d = 2
    while x > 1:
        c = 0
        while x % d == 0:
            x //= d
            c += 1
        e[d] += c
        d += 1


# 75
# 25 3
# 15 5
# 5 5 3

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


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

Submission status: Accepted

Solution code:
def f(p,N):
    res=0
    while N>=p:
        N//=p
        res+=N
    return res

N=int(input())
ps=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
A=[len([p for p in ps if f(p,N)>=k]) for k in [2,4,14,24,74]]

a,b,c,d,e=A[0],A[1],A[2],A[3],A[4]

ans=0
# 3*5^2
ans+=b*(b-1)//2*(a-2)
# 3*25
ans+=d*(a-1)
# 5*15
ans+=c*(b-1)
# 75
ans+=e

print(ans)

Submission status: Accepted

Solution code:
import sys
n=int(input())
data=[0]*(n+1)
for i in range(2,n+1):
    for j in range(2,int(i**(1/2))+1):
        if i%j==0:
            break
    else:
        count=0
        for j in range(i,n+1):
            k=j
            while k%i==0:
                k//=i
                data[i]+=1
if n==1:
    print(0)
    sys.exit()
if data[2]>=74:
    ans=1
else:
    ans=0
count3=0
count5=0
count15=0
count25=0
for i in range(n+1):
    if data[i]>=2:
        count3+=1
for i in range(n+1):
    if data[i]>=4:
        count5+=1
for i in range(n+1):
    if data[i]>=14:
        count15+=1
for i in range(n+1):
    if data[i]>=24:
        count25+=1
ans+=count25*(count3-1)
ans+=count15*(count5-1)
ans+=(count3-2)*count5*(count5-1)//2
print(ans)

Submission status: Accepted

Solution code:
# ABC114D - 756
from collections import defaultdict


def prime_factorization(x: int) -> dict:
    max_prime, ret = 0, {}
    cnt = 0
    while x % 2 == 0:  # divide x by 2 as much as possible
        x //= 2
        cnt += 1
    if cnt > 0:
        max_prime = 2
        ret[max_prime] = cnt

    cnt = 0
    for i in range(3, int(x ** 0.5) + 1, 2):
        cnt = 0
        while x % i == 0:
            x //= i
            max_prime = i
            cnt += 1
        if cnt > 0:
            ret[max_prime] = cnt

    if x > 2:  # when x is prime greater than 2
        max_prime = x
        ret[max_prime] = 1
    return ret


def count(n: int) -> int:
    return sum(i >= n - 1 for i in prime_factors.values())


def main():
    global prime_factors
    N = int(input())
    prime_factors = defaultdict(int)
    for i in range(2, N + 1):
        for k, v in prime_factorization(i).items():
            prime_factors[k] += v
    ans = (
        count(75)
        + count(25) * (count(3) - 1)
        + count(15) * (count(5) - 1)
        + count(5) * (count(5) - 1) * (count(3) - 2) // 2
    )
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
f=list()

for i in range(1,n+1):
  b=2
  while b*b <= i:
    while i%b==0:
      i //= b
      f.append(b)
    b += 1
  if i > 1:
    f.append(i)

o2=o3=o4=o14=o24=o74=0

for i in range(2,n+1):
  d=f.count(i)
  if d>=2:
    o2 += 1
  if d>=4:
    o4 += 1
  if d>=14:
    o14 += 1
  if d>=24:
    o24 += 1
  if d>=74:
    o74 += 1

print(o4*(o4-1)//2*(o2-2)+o14*(o4-1)+o24*(o2-1)+o74)

Submission status: Accepted

Solution code:
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]
lists=[[0 for i in range(101)] for i in range(101)]
for p in prime:
    for n in range(1,101):
        if n==1:
            lists[p][n]=0
        else:
            if n%p!=0:
                lists[p][n]= lists[p][n-1]
        
            elif n%p==0:
                count=1
                order=0
                OK=True
                while OK:
                    if n%(p**count)==0:
                        order=count
                        count+=1
                    else:
                        OK=False
                lists[p][n]=lists[p][n-1]+(count-1)
       


n=int(input())
uselist=[]
for p in prime:
    uselist.append(lists[p][n])


dictio={}
for i in range(len(prime)):
    dictio[prime[i]]=uselist[i]

ans=0


larger_74=0
larger_24=0
larger_14=0
larger_2=0
larger_4=0

for  i in dictio.values():
    if i>=74:
        ans+=1
    if i>=24:
        larger_24+=1
    if i>=14:
        larger_14+=1
    if i>=4:
        larger_4+=1
    if i>=2:
        larger_2+=1

if larger_74>=1:
    answer+=1
if larger_14>=1 and larger_4>=2:
    ans+=(larger_14)*(larger_4-1)
if larger_24>=1 and larger_2>=2:
    ans+=(larger_24)*(larger_2-1)
if larger_4>=2 and larger_2>=3:
    ans+=((larger_4)*(larger_4-1)//2)*(larger_2-2)
print(ans)

Submission status: Accepted

Solution code:
import collections

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

N = int(input())
if N == 1:
  print(0)
  exit()
PD = {}
for i in range(2,N+1):
  c = collections.Counter(prime_factorize(i))
  #print(i,c)
  for k,v in c.items():
    if k in PD:
      PD[k] += v
    else:
      PD[k] = v
#print(PD)
o74 = 0
o24 = 0
o14 = 0
o4 = 0
o2 = 0
for v in PD.values():
  if v >= 74:
    o74 += 1
  if v >= 24:
    o24 += 1
  if v >= 14:
    o14 += 1
  if v >= 4:
    o4 += 1
  if v >= 2:
    o2 += 1
#print(o74,o24,o14,o4,o2)
ans = o74
if o24 > 0 and o2 > 1:
  ans += o24*(o2-1)
if o14 > 0 and o4 > 1:
  ans += o14*(o4-1)
if o4 > 1 and o2 > 2:
  ans += o4*(o4-1)//2*(o2-2)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
A = [0] * 100

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

x = len([x for x in A if x >= 4])
y = len([x for x in A if x >= 2])
z = len([x for x in A if x >= 14])
w = len([x for x in A if x >= 4])
a = len([x for x in A if x >= 24])
b = len([x for x in A if x >= 2])

print(((x * (x - 1)) // 2) * (y - 2) + z * (w - 1) + a * (b - 1) + len([x for x in A if x >= 74]))

Submission status: Accepted

Solution code:
n=int(input());c=[1]*101
for i in range(2,n+1):
    for j in range(2,n+1):
        while i%j==0:i/=j;c[j]+=1
def N(M):return len([0 for x in c if x>=M])
print(N(75)+N(25)*~-N(3)+N(15)*~-N(5)+N(5)*~-N(5)//2*~-~-N(3))

Submission status: Accepted

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

san = 0; go = 0; jugo = 0; nijugo = 0; shitigo = 0
for i in range(2, 101):
    if cnt[i] >= 3: san += 1
    if cnt[i] >= 5: go += 1
    if cnt[i] >= 15: jugo += 1
    if cnt[i] >= 25: nijugo += 1
    if cnt[i] >= 75: shitigo += 1

print(shitigo + nijugo*(san-1) + jugo*(go-1) + go*(go-1)//2*(san-2))

Submission status: Accepted

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr

n = int(input())
exponent = [[0]*(n+1) for i in range(n+1)]

for i in range(2,n+1):
  for j in range(n+1):
    exponent[i][j] += exponent[i-1][j]
  Fi = factorization(i)
  for f in Fi:
    exponent[i][f[0]] += f[1]

c75,c25,c15,c5,c3 = 0,0,0,0,0
for e in exponent[n]:
  if e >= 74:
    c75 += 1
  if e >= 24:
    c25 += 1
  if e >= 14:
    c15 += 1
  if e >= 4:
    c5 += 1
  if e >= 2:
    c3 += 1
print(
  c75 + c25*(c3-c25)+c25*(c25-1) + c15*(c5-c15)+c15*(c15-1) + (c5*(c5-1))//2*(c5-2)+(c5*(c5-1))//2*(c3-c5)
    )

Submission status: Accepted

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


def yakusuu(n,p):
    res = 0
    while n > 0:
        n //= p
        res += n
    return res

l2 = 0
l4 = 0
l14 = 0
l24 = 0
l74 = 0

for p in prime:
    y = yakusuu(n,p)
    if y >= 2:
        l2 += 1
    if y >= 4:
        l4 += 1
    if y >= 14:
        l14 += 1
    if y >= 24:
        l24 += 1
    if y >= 74:
        l74 += 1

print(l4*(l4-1)*(l2-2)//2+l14*(l4-1)+l24*(l2-1)+l74)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
if N == 1:
	print(0)
	sys.exit()

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

e = [0] * (N+1)
for i in range(2, N+1):
	for x in factorization(i):
		e[x[0]] += x[1]

# print(e)

ans = 0

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

# 同じ素数はとらないように選択, 3*5*5のときは重複するので2で割る
print(num(75)+num(25)*(num(3)-1)+num(15)*(num(5)-1)+num(5)*(num(5)-1)*(num(3)-2)//2)