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

fact_ct = [0 for _ in range(N+1)]
pr = []

def primes():
  ans = set()
  visited = set()
  for p in range(2,N+1):
    if p in visited:
      continue
    ans.add(p)
    q = p
    while q <= N:
      visited.add(q)
      q += p    
  return ans

pr = primes() 

def add_fact_ct(n):
  visited = set()
  for p in range(2,N+1):
    if p not in pr:
      continue
    while n % p == 0:
      fact_ct[p] += 1
      n //= p  

for n in range(2, N+1):
  add_fact_ct(n)
  
ct_75 = 0
ct_25 = 0
ct_15 = 0
ct_5 = 0
ct_3 = 0
ct_1 = 0
  
for ct in fact_ct:
  if ct >= 74:
    ct_75 += 1
  if ct >= 24:
    ct_25 += 1
  if ct >= 14:
    ct_15 += 1
  if ct >= 4:
    ct_5 += 1 
  if ct >= 2:
    ct_3 += 1

ans = 0

ans += ct_75

ans += ct_25 * (ct_3-1)
ans += ct_15 * (ct_5-1)

ans += ct_5*(ct_5-1)*(ct_3-2) // 2

print(ans)
#print(fact_ct)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("YES") if fl else print("NO")
import collections
import math
import itertools
import heapq as hq
import sys

n = ni()
def factorize(n):
    b = 2
    fct = [(1,1)]
    while b * b <= n:
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        b = b + 1
    if n > 1:
        fct.append((n,1))
    return fct

co = collections.Counter()
for i in range(2,n+1):
    fct = factorize(i)
    for num,cnt in fct:
        if num>1:
            co[num]+=cnt
f4 = 0
f2 = 0
f14 = 0
f24=0
f74=0
for cnt in co.values():
    if cnt>=74:
        f74+=1
    if cnt>=24:
        f24+=1
    if cnt>=14:
        f14+=1
    if cnt>=4:
        f4+=1
    if cnt>=2:
        f2+=1



ans = f74 + f24*(f2-1) +f14*(f4-1)+f4*(f4-1)//2*(f2-2)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

if n < 10:
    print(0)
    exit()

prime = [2, 3]
for i in range(5, n+1, 2):
    for p in prime:
        if i % p == 0:
            break
    else:
        prime.append(i)

# factrization
num = []
for p in prime:
    cnt = 1
    now = p
    while now <= n:
        cnt += n // now
        now *= p
    num.append(cnt)

more3 = [i for i in num if i >= 3]
more5 = [i for i in more3 if i >= 5]
more15 = [i for i in more5 if i >= 15]
more25 = [i for i in more15 if i >= 25]
more75 = [i for i in more25 if i >= 75]

more3 = len(more3); more5 = len(more5); more15 = len(more15); more25 = len(more25); more75 = len(more75)

print(more25 * (more3 - 1) + more15 * (more5 - 1) + more5 * (more5 - 1) * (more3 - 2) // 2 + more75)

Submission status: Accepted

Solution code:
import sys
import math
import itertools


# \n
def input():
    return sys.stdin.readline().rstrip()


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)

    if temp != 1:
        arr.append(temp)

    if arr == []:
        arr.append(n)
    return arr


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

    P = [0] * (N + 1)

    for i in range(1, N + 1):
        arr = factorization(i)
        for s in arr:
            P[s] += 1

    ans = 0
    PN = []
    for j in P:
        if j != 0:
            PN.append(j)

    ans = 0
    count = 0
    # 75**
    for i in PN:
        if i >= 74:
            count += 1
    ans += count

    count = 0
    # 25*3
    sub1 = 0
    sub2 = 0
    for i in PN:

        if i >= 24:
            sub1 += 1
        if i >= 2:
            sub2 += 1
    ans += sub1 * (sub2 - 1)

    # 15*5
    sub1 = 0
    sub2 = 0
    for i in PN:

        if i >= 14:
            sub1 += 1
        if i >= 4:
            sub2 += 1
    ans += sub1 * (sub2 - 1)

    # 5*5*3
    sub1 = 0
    sub2 = 0
    for i in PN:

        if i >= 4:
            sub1 += 1
        if i >= 2:
            sub2 += 1
    ans += sub1 * (sub1 - 1)*(sub2-2)//2


    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


def factorize(N):  # 素因数分解
    p = 2 
    while p * p <= N:
        while N % p == 0:
            N //= p
            fact[p] += 1
        p += 1
    if N > 1:
        fact[N] += 1

n = int(input())

fact = defaultdict(int)
for i in range(n):
    factorize(i + 1)

cnt = {2: 0, 4: 0, 14: 0, 24: 0, 74: 0}
for vfact in fact.values():
    for i in cnt:
        cnt[i] += (vfact >= i)

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

Submission status: Accepted

Solution code:
from collections import defaultdict


def factorize(N):  # 素因数分解
    p = 2 
    while p * p <= N:
        while N % p == 0:
            N //= p
            fact[p] += 1
        p += 1
    if N > 1:
        fact[N] += 1

n = int(input())
fact = defaultdict(int)
for i in range(n):
    factorize(i + 1)

cnt4 = sum(cnt >= 4 for cnt in fact.values())
cnt2 = sum(cnt >= 2 for cnt in fact.values())
cnt24 = sum(cnt >= 24 for cnt in fact.values())
cnt14 = sum(cnt >= 14 for cnt in fact.values())
cnt74 = sum(cnt >= 74 for cnt in fact.values())

ans = cnt4 * (cnt4 - 1) * (cnt2 - 2) // 2
ans += cnt24 * (cnt2 - 1) + (cnt4 - 1) * cnt14 + cnt74
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#D - 756
import sys 
import math
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())

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

cnt = defaultdict(int)
for i in range(2,N+1):
    prime_factorize(i,cnt)
# n以上の個数を返す
def num(n):
    c = 0
    for v in cnt.values():
        if v < n:
            break
        c += 1
    return c 

print(num(74) + num(24)*(num(2)-1) + num(14)*(num(4)-1) + num(4)*(num(4)-1)*(num(2)-2)//2)

Submission status: Accepted

Solution code:
n = int(input())

prime_1 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
prime_2 = [4,9,25,49]
prime_3 = [8,27]
prime_4 = [16,81]

dp = [0]*15

for i in range(15):
    dp[i] += n // prime_1[i]

for j in range(4):
    dp[j] += n // prime_2[j]
    
for k in range(2):
    dp[k] += n // prime_3[k]

for l in range(2):
    dp[l] += n // prime_4[l]

dp[0] += n // 32
dp[0] += n // 64

n2 = sum(x>1 for x in dp) 
n4 =sum(x>3 for x in dp)
n14=sum(x>13 for x in dp)
n24=sum(x>23 for x in dp)
n74=sum(x>73 for x in dp)

p553 = (n2-n4) * (n4*(n4-1) //2 ) + ((n4*(n4-1)*(n4-2))//2)
p144 = (n4-n14) * n14 + (n14*(n14-1))
p242 = (n2-n24) * n24 + (n24*(n24-1))
p750 = n74

print(p553+p144+p242+p750)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

n = int(input())

# Eratosthenes' sieve
is_prime = [True for _ in range(100)]
is_prime[0] = is_prime[1] = False
for i in range(100):
    if not is_prime[i]:continue 
    for j in range(i*i, 100, i): 
        if not is_prime[j]: 
            is_prime[j] = False

factor = [0 for _ in range(100)]
for i in range(2, n+1):
    for j in range(2, 100):
        if is_prime[j]:
            while i%j == 0:
                factor[j] += 1
                i //= j

#print('is_prime =', is_prime)
#print('factor =', factor)

fs = []
for i in range(100):
    if factor[i] != 0:
        fs.append(factor[i])

#print('fs =', fs)

m = len(fs)
ans = [0 for _ in range(4)]
for i in range(m):
    for j in range(m):
        for k in range(m):
            if i!=j and j!=k and k!=i:
                if fs[i] >= 4 and fs[j] >= 4 and fs[k] >=2:
                    ans[0] += 1
#                    print('fs[{}] = {}, fs[{}] = {}, fs[{}] = {}'.format(i, fs[i], j, fs[j], k, fs[k]))
for i in range(m):
    if fs[i] >= 74: 
        ans[1] += 1
#        print('fs[{}] = {}'.format(i, fs[i]))
for i in range(m):
    for j in range(m):
        if i!=j:
            if fs[i] >= 2 and fs[j] >= 24: 
                ans[2] += 1
#                print('fs[{}] = {}, fs[{}] = {}'.format(i, fs[i], j, fs[j]))
for i in range(m):
    for j in range(m):
        if i!=j:
            if fs[i] >= 4 and fs[j] >= 14: 
                ans[3] += 1
#                print('fs[{}] = {}, fs[{}] = {}'.format(i, fs[i], j, fs[j]))

Ans = ans[0]//2 + ans[1] + ans[2] + ans[3]
print(Ans)

Submission status: Accepted

Solution code:
# 素因数分解
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(2, n+1):
    p = prime_factorize(i)
    for cp in p:
        if cp in d:
            d[cp] += 1
        else:
            d[cp] = 1

cnt = {75:0, 25:0, 15:0, 5:0, 3:0}
for i in d:
    for j in cnt:
        if d[i] >= j-1:
            cnt[j] += 1
ans = cnt[75] + cnt[25]*(cnt[3]-1) + cnt[15]*(cnt[5]-1) + cnt[5]*(cnt[5]-1)//2*(cnt[3]-2)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
c = (N+1)*[0]

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

f = lambda x:sum(y+1>=x for y in c)
print(f(75)+f(25)*(f(3)-1)+f(15)*(f(5)-1)+f(5)*(f(5)-1)//2*(f(3)-2))

Submission status: Accepted

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

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])
            fac[i] += cnt

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

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

for num in range(2, N+1):
    factorization(num)

ans = 0

num_74 = set()
num_24 = set()
num_14 = set()
num_4 = set()
num_2 = set()
for key, value in fac.items():
    if value >= 74:
        num_74.add(key)
    if value >= 24:
        num_24.add(key)
    if value >= 14:
        num_14.add(key)
    if value >= 4:
        num_4.add(key)
    if value >= 2:
        num_2.add(key)
#1
ans += len(num_74)

#2
ans += len(num_24) * (len(num_2)-1)
# ans += len(num_2.difference(num_24)) * (len(num_24))*(len(num_24)-1)//2 + len(num_24) * (len(num_24)-1)*(len(num_24)-2)//2


#3
ans += len(num_14) * (len(num_4) - 1)
# ans += len(num_4.difference(num_14)) * (len(num_14))*(len(num_14)-1)//2 + len(num_14) * (len(num_14)-1) * (len(num_14) - 2) //2

#4
ans += len(num_2.difference(num_4)) * len(num_4)*(len(num_4)-1)//2 + len(num_4) * (len(num_4)-1)*(len(num_4)-2)//2


print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

count = Counter([])

N = int(input())

for i in range(2,N+1):
    n = i
    tmp = []
    d = 2
    while d <= n:
        while n%d == 0:
            n //= d
            tmp.append(d)
        d += 1
    count += Counter(tmp)

ans = 0
#74個以上の次数をもつ素因数を探す
for v in count.values():
    if v >= 74:
        ans += 1

#24,2個以上の次数の組み合わせ
more24 = 0
more2 = 0
for v in count.values():
    if v >= 2:
        more2 += 1
    if v >= 24:
        more24 += 1

ans += more24*(more2-more24)
ans += more24*(more24-1)

#14,4個以上の次数の組み合わせ
more14 = 0
more4 = 0
for v in count.values():
    if v >= 4:
        more4 += 1
    if v >= 14:
        more14 += 1
ans += more14 * (more4-more14)
ans += more14*(more14-1)

#4,4,2個以上の次数の組み合わせ
ans += more4*(more4-1)//2 * (more2-more4)
ans += more4*(more4-1)//2*(more4-2)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
primes = list(range(2,101))
for i in range(len(primes)):
    if primes[i]:
        j = i
        j += primes[i]
        while j < len(primes):
            primes[j] = None
            j += primes[i]
primes = [p for p in primes if p]
N = int(input())
fact = defaultdict(int)
for p in primes:
    i = p
    while i <= N:
        fact[p] += N//i
        i *= p
f2 = set()
f4 = set()
f14 = set()
f24 = set()
f74 = set()
for p in fact:
    if fact[p] >= 2:
        f2.add(p)
    if fact[p] >= 4:
        f4.add(p)
    if fact[p] >= 14:
        f14.add(p)
    if fact[p] >= 24:
        f24.add(p)
    if fact[p] >= 74:
        f74.add(p)
ans = 0
ans += len(f74)
ans += len(f24)*(len(f2)-1)
ans += len(f14)*(len(f4)-1)
ans += (len(f2)-2)*len(f4)*(len(f4)-1)//2
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

prime_factor = {1: 1} if n == 1 else {}
for i in range(2, n+1):
    while i % 2 == 0:
        prime_factor[2] = prime_factor.get(2, 0) + 1
        i //= 2
    f = 3
    while f * f <= i:
        if i % f == 0:
            prime_factor[f] = prime_factor.get(f, 0) + 1
            i //= f
        else:
            f += 2
    if i != 1:
        prime_factor[i] = prime_factor.get(i, 0) + 1

m = len(prime_factor)
prime = list(prime_factor.keys())

dp = [[0]*76 for _ in range(m+2)]
dp[0][1] = 1
for i in range(m):
    for j in range(76):
        for k in range(prime_factor[prime[i]]+1):
            if (v := j * (k+1)) < 76:
                dp[i+1][v] += dp[i][j]

print(dp[m][75])

Submission status: Accepted

Solution code:
n=int(input())
w=[0 for i in range(101)]
for m in range(2,n+1):
    tmp=m
    for j in range(2,m+1):
        while tmp%j==0:
            w[j]+=1
            tmp//=j
def num(a):
    return len(list(filter(lambda x:x>=a-1,w)))
print(num(75)+num(25)*(num(3)-1) + num(15) * (num(5) - 1)
+ num(5) * (num(5) - 1) * (num(3) - 2) // 2)

Submission status: Accepted

Solution code:
import sys
n = int(input())
# 1とかの時例外処理

import math
def nCr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def factorization(n):
    '''
    [base,power]のリストを返す
    '''
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 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

base_power = [0] * 100
for i in range(2,n+1):
    arr = factorization(i)
    for base, power in arr:
        base_power[base] += power

More_2 = 0
More_4 = 0
More_14 = 0
More_24 = 0
More_74 = 0
for base in range(100):
    if base_power[base] >= 2:
        More_2 += 1
    if base_power[base] >= 4:
        More_4 += 1
    if base_power[base] >= 14:
        More_14 += 1
    if base_power[base] >= 24:
        More_24 += 1
    if base_power[base] >= 74:
        More_74 += 1

ans = 0
if More_2 - 2 > 0 and More_4 >= 2:
    ans += nCr(More_4,2)*(More_2-2)
if More_2 - 1 > 0 and More_24 > 0:
    ans += More_24 * (More_2-1)
if More_14 > 0 and More_4-1>0:
    ans += More_14 * (More_4-1)
if More_74 > 0:
    ans += More_74
print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def primeFactorization(n):
    ans = []
    temp = n
    while temp%2 == 0:
        ans.append(2)
        temp //= 2
    for i in range(3, int(n**0.5)+1, 2):
        while temp%i == 0:
            ans.append(i)
            temp //= i
    if temp > 1:
        ans.append(temp)
    return collections.Counter(ans)

def resolve():
    N = I()

    # N!の素因数を求める
    pf_N_fact = collections.Counter()
    for i in range(1, N + 1):
        pf = primeFactorization(i)
        for k, v in pf.items():
            pf_N_fact[k] += v
    l = list(pf_N_fact.values())
    l.sort()
    pf_num = len(pf_N_fact)

    # 約数75個: 素因数の個数+1の積が75になるように組み合わせる
    # 素因数の個数を以下の組み合わせで何通り取れるかを調べる
    # (2, 4, 4), (2, 24), (4, 14), (74)
    ans = 0
    num_2 = pf_num - bisect.bisect_left(l, 2)
    num_4 = pf_num - bisect.bisect_left(l, 4)
    num_14 = pf_num - bisect.bisect_left(l, 14)
    num_24 = pf_num - bisect.bisect_left(l, 24)
    num_74 = pf_num - bisect.bisect_left(l, 74)
    ans += num_4 * (num_4 - 1) // 2 * (num_2 - 2)
    ans += num_24 * (num_2 - 1)
    ans += num_14 * (num_4 - 1)
    ans += num_74
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def primeFactorization(n):
    ans = []
    temp = n
    while temp%2 == 0:
        ans.append(2)
        temp //= 2
    for i in range(3, int(n**0.5)+1, 2):
        while temp%i == 0:
            ans.append(i)
            temp //= i
    if temp > 1:
        ans.append(temp)
    return collections.Counter(ans)

def resolve():
    N = I()

    # N!の素因数を求める
    pf_N_fact = collections.Counter()
    for i in range(1, N + 1):
        pf = primeFactorization(i)
        for k, v in pf.items():
            pf_N_fact[k] += v
    l = list(pf_N_fact.values())
    l.sort()
    pf_num = len(pf_N_fact)

    # 約数75個: 素因数の個数+1の積が75になるように組み合わせる
    # 素因数の個数を以下の組み合わせで何通り取れるかを調べる
    # (2, 4, 4), (2, 24), (4, 14), (74)
    ans = 0
    num_2 = pf_num - bisect.bisect_left(l, 2)
    num_4 = pf_num - bisect.bisect_left(l, 4)
    num_14 = pf_num - bisect.bisect_left(l, 14)
    num_24 = pf_num - bisect.bisect_left(l, 24)
    num_74 = pf_num - bisect.bisect_left(l, 74)
    ans += num_4 * (num_4 - 1) // 2 * max(num_2 - 2, 0)
    ans += num_24 * max(num_2 - 1, 0)
    ans += num_14 * max(num_4 - 1, 0)
    ans += num_74
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import collections

def fact(N):
    arr = []
    i=2
    while i*i<=N:
        if N%i==0:
            while N%i==0:
                arr.append(i)
                N//=i
        i+=1
    if N>1:
        arr.append(N)
    return arr

N=int(input())
arr = []
for i in range(1,N+1):
    arr += fact(i)
#print(arr)
arc=collections.Counter(arr)
num74cnt=0
num24cnt=0
num14cnt=0
num4cnt=0
num2cnt=0
for val in arc.values():
    if val >=74:
        num74cnt+=1
    if val >=24:
        num24cnt+=1
    if val >=14:
        num14cnt+=1
    if val >= 4:
        num4cnt+=1
    if val >= 2:
        num2cnt +=1
ans = num74cnt
ans += num24cnt*(num2cnt-1)
ans += num14cnt*(num4cnt-1)
ans += num4cnt*(num4cnt-1)//2*(num2cnt-2)

print(ans)

Submission status: Accepted

Solution code:
from collections import *

def factorize(n):
    fct = []
    
    for i in range(2, int(n**0.5)+1):
        c = 0
        
        while n%i==0:
            n //= i
            c += 1
        
        if c>0:
            fct.append((i, c))

    if n!=1:
        fct.append((n, 1))
    
    return fct

N = int(input())
cnt = defaultdict(int)

for i in range(1, N+1):
    fct = factorize(i)
    
    for p, c in fct:
        cnt[p] += c

c2, c4, c14, c24, c74 = 0, 0, 0, 0, 0

for v in cnt.values():
    if v>=2:
        c2 += 1
        
    if v>=4:
        c4 += 1
        
    if v>=14:
        c14 += 1
        
    if v>=24:
        c24 += 1
        
    if v>=74:
        c74 += 1

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

Submission status: Accepted

Solution code:
"""
実際にN!を計算するわけには行かない。
memo[n] => nの素因数分解の結果

sum(memo[N])の素因数分解の結果から
"""
from collections import Counter
N = int(input())
memo = [None]*(N+1)

for i in range(2,N+1):
    tmp = []
    n = i
    d = 2
    while n!=1:
        while n%d==0:
            tmp.append(d)
            n//=d
        d += 1
    memo[i] = Counter(tmp)

count = Counter([])
for i in range(2,N+1):
    count += memo[i]

ans = 0
#数が74個以上ある素因数の数
c74 = 0
#数が24個以上ある素因数の数
c24 = 0
#数が14個以上ある素因数の数
c14 = 0
#数が4個以上ある素因数の数
c4 = 0
#数が2個以上ある素因数の数
c2 = 0

for v in count.values():
    if v >= 2:
        c2 += 1
    if v >= 4:
        c4 += 1
    if v >= 14:
        c14 += 1
    if v >= 24:
        c24 += 1
    if v >= 74:
        c74 += 1

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


"""
#1つの素因数で75数を形成できるパターンをみつける
for k,v in count.items():
    if v >= 74:
        ans += 1
    
#2つの素因数(a,b)で3,25のパターンで、75数を形成できるパターンを見つける
for k,v in count.items():
    if v >= 24:
        for k2,v2 in count.items():
            if k2 != k and v2 >= 2:
                ans += 1

#2つの素因数(a,b)で5,15のパターンで、75数を形成できるパターンを見つける
for k,v in count.items():
    if v >= 14:
        for k2,v2 in count.items():
            if k2 != k and v2 >= 4:
                ans += 1

#2つの素因数(a,b)で3,25のパターンで、75数を形成できるパターンを見つける
for k,v in count.items():
    if v >= 4:
        for k2,v2 in count.items():
            if k2 != k and v2 >= 4:
                for k3,v3 in count.items():
                    if k3 != k and k3!=k2 and v3 >= 2:
                        ans += 1
"""

print(ans)

Submission status: Accepted

Solution code:

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


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


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

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
prm = defaultdict(int)
for n in range(2, N+1):
    for p in range(2, int(n**0.5)+2):
        while n % p == 0:
            prm[p] += 1
            n //= p
        if n == 1:
            break
    else:
        prm[n] += 1
C = [2, 4, 14, 24, 74]
cnt = [0]*5
for p, x in prm.items():
    for i, c in enumerate(C):
        if x >= c:
            cnt[i] += 1
c2, c4, c14, c24, c74 = cnt

ans = c4*(c4-1)//2*(c2-2) if c2 > 2 else 0
ans += max(0, c24*(c2-1))
ans += max(0, c14*(c4-1))
ans += c74
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


N = int(input())
dict = defaultdict(int)


def prime_factorize(n):  # nを素因数分解してdictに保存
    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)
    for ai in a:
        dict[ai] += 1


for i in range(1, N + 1):  # N!の素因数分解に相当する
    prime_factorize(i)

ans = 0

# p**4 * q**4 * r**2
for k1, v1 in dict.items():
    for k2, v2 in dict.items():
        for k3, v3 in dict.items():
            if k1 < k2 < k3:
                if v1 >= 2 and v2 >= 4 and v3 >= 4:
                    ans += 1
                if v1 >= 4 and v2 >= 2 and v3 >= 4:
                    ans += 1
                if v1 >= 4 and v2 >= 4 and v3 >= 2:
                    ans += 1

for k1, v1 in dict.items():
    for k2, v2 in dict.items():
        if k1 < k2:
            # p**14 * q**4
            if v1 >= 14 and v2 >= 4:
                ans += 1
            if v1 >= 4 and v2 >= 14:
                ans += 1
            # p**24 * q*2
            if v1 >= 24 and v2 >= 2:
                ans += 1
            if v1 >= 2 and v2 >= 24:
                ans += 1

# p**74
for k1, v1 in dict.items():
    if v1 >= 74:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


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)
    for ai in a:
        dict[ai] += 1


N = int(input())
dict = defaultdict(int)


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)
    for ai in a:
        dict[ai] += 1


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

ans = 0

# p**4 * q**4 * r**2
for k1, v1 in dict.items():
    for k2, v2 in dict.items():
        for k3, v3 in dict.items():
            if k1 < k2 < k3:
                if v1 >= 2 and v2 >= 4 and v3 >= 4:
                    ans += 1
                if v1 >= 4 and v2 >= 2 and v3 >= 4:
                    ans += 1
                if v1 >= 4 and v2 >= 4 and v3 >= 2:
                    ans += 1

# p**14 * q**4
# p**24 * q*2
for k1, v1 in dict.items():
    for k2, v2 in dict.items():
        if k1 < k2:
            if v1 >= 14 and v2 >= 4:
                ans += 1
            if v1 >= 4 and v2 >= 14:
                ans += 1
            if v1 >= 24 and v2 >= 2:
                ans += 1
            if v1 >= 2 and v2 >= 24:
                ans += 1

# p**74
for k1, v1 in dict.items():
    if v1 >= 74:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	if n <= 9:
		return 0
	
	counter = collections.defaultdict(lambda :0)
	for i in range(2,n+1):
		v=i
		for ww in range(2,100):
			if v < ww:
				break
			while v%ww==0:
				counter[ww]+=1
				v=v//ww
				
	#for k in counter:
	#	print(k,counter[k])
	
	ret = 0
	#a**74
	for k in counter:
		if counter[k] >= 74:
			ret += 1
	
	#a**24 * b** 2
	n24 = 0
	n2 = 0
	for k in counter:
		if counter[k] >= 24:
			n24 += 1
		elif counter[k] >= 2:
			n2 += 1
	ret += (n24 * (n24-1))
	ret += n24 * n2
		
	#a**14 * b**4
	n14 = 0
	n4 = 0
	for k in counter:
		if counter[k] >= 14:
			n14 += 1
		elif counter[k] >= 4:
			n4 += 1
	ret += (n14 * (n14-1))
	ret += n14 * n4
	
	#a**4 * b**4 * c**2
	n4 = 0
	n2 = 0
	for k in counter:
		if counter[k] >= 4:
			n4 += 1
		elif counter[k] >= 2:
			n2 += 1
	ret += (n4 * (n4-1) * (n4 - 2)) // 2
	ret += ((n4 * (n4-1)) // 2 ) * n2
	
	return ret
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
from collections import*
def cont(n):
  res=0
  n-=1
  for i in c:
    if i>=n:res+=1
  return res
def fact_p(n):
  m=n
  i=2
  a=[]
  while n>1:
    if i>m**.5:
      a+=[n]
      break
    if n%i==0:
      n//=i
      a+=[i]
    else:i+=1  
  return a
n=int(input())
a=[]
for i in range(1,n+1):
  a+=fact_p(i)
c=list(Counter(a).values())
print(cont(75)+cont(25)*(cont(3)-1)+cont(15)*(cont(5)-1)+cont(5)*(cont(5)-1)*(cont(3)-2)//2)

Submission status: Accepted

Solution code:
N=int(input())

def primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n+1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

x=primes(N//2+1)
s=[0]*len(x)

for n,i in enumerate(x):
    for j in range(1,7):
        if i**j > N:
            break
        s[n]+=N//(i**j)

c2=0
c4=0
c14=0
c24=0
c74=0
for i in s:
    if i>=2:
        c2+=1
        if i>=4:
            c4+=1
            if i>=14:
                c14+=1
                if i>=24:
                    c24+=1
                    if i>=74:
                        c74+=1
    else:
        break

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

Submission status: Accepted

Solution code:
sosuu=[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())
L=[0 for i in range(25)]
for i in range(25):
  s=N
  while True:
    if s!=0:
      s=s//sosuu[i]
      L[i]+=s
    else:
      break
#1 75 3 25 5 15 (3 5 5)
a,b,c,d,e=0,0,0,0,0
for i in range(25):
  if L[i]>=74:
    a+=1
  if L[i]>=24:
    b+=1
  if L[i]>=14:
    c+=1
  if L[i]>=4:
    d+=1
  if L[i]>=2:
    e+=1
print(a+b*(e-1)+c*(d-1)+d*(d-1)*(e-2)//2)

Submission status: Accepted

Solution code:
class PrimeFactor():

    def __init__(self, n):
        """
        エラトステネス　O(N loglog N)
        """
        self.n = n
        self.table = list(range(n+1))       # 最小素因数のリスト
        self.table[2::2] = [2]*(n//2)
        for p in range(3, int(n**0.5) + 2, 2):
            if self.table[p] == p:
                for q in range(p * p, n + 1, 2 * p):
                    if self.table[q] == q:
                        self.table[q] = p

    def is_prime(self, x):
        """ 素数判定　O(1) """
        if x < 2:
            return False
        return self.table[x] == x

    def prime_factors(self, x):
        """ 素因数分解 O(logN)  (試し割りだとO(sqrt(N))) """
        res = []
        if x < 2:
            return res
        while self.table[x] != 1:
            res.append(self.table[x])
            x //= self.table[x]
        return res

    def prime_counter(self, x):
        """ 素因数分解（個数のリスト） O(logN) """
        res = dict()
        if x < 2:
            return res
        while self.table[x] != 1:
            res[self.table[x]] = res.get(self.table[x], 0) + 1
            x //= self.table[x]
        return res

#################################################################
N = int(input())
P = PrimeFactor(N)
Q = dict()
for i in range(1,N+1):
    for key, value in P.prime_counter(i).items():
        Q[key] = Q.get(key,0) + value
a, b, c, d, e = 0, 0, 0, 0, 0
for value in Q.values():
    if value >= 2: a += 1
    if value >= 4: b += 1
    if value >= 24: c += 1
    if value >= 14: d += 1
    if value >= 74: e += 1
print(b*(b-1)//2*(a-2) + c*(a-1) + d*(b-1) + e)