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

from collections import Counter
import math

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

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

L = []
for i in range(1, N+1):
    prime = prime_factorize(i)
#    print(i, prime)
    L += prime
C = Counter(L)
#print(C)


def count_n(C, n):
    return [v >= n for v in C.values()].count(True)

count_4 = count_n(C, 4)
count_2 = count_n(C, 2)
count_14 = count_n(C, 14)
count_24 = count_n(C, 24)
count_74 = count_n(C, 74)


c4_442 = count_4
c2_442 = count_2 - 2

if c4_442 < 2 or c2_442 < 1:
    ans442 = 0
else:
    ans442 = combinations_count(c4_442, 2)*combinations_count(c2_442, 1)

c14_144 = count_14
c4_144 = count_4 - 1
if c14_144 < 1 or c4_144 < 1:
    ans144 = 0
else:
    ans144 = combinations_count(c14_144, 1)*combinations_count(c4_144, 1)

c24_242 = count_24
c2_242 = count_2 - 1
if c24_242 < 1 or c2_242 < 1:
    ans242 = 0
else:
    ans242 = combinations_count(c24_242, 1)*combinations_count(c2_242, 1)
    
c74_74 = count_74
if c74_74 < 1:
    ans74 = 0
else:
    ans74 = combinations_count(c74_74, 1)
    
print(ans442+ans144+ans242+ans74)

Submission status: Accepted

Solution code:
from itertools import permutations
# 3*5*5
# (2, 4, 4) (14, 4) (2, 24) (74)
n = int(input())
d = [0] * (n + 1)
for i in range(2, n + 1):
    for p in range(2, n + 1):
        while i % p == 0:
            i //= p
            d[p] += 1
d = list(filter(int, d))
ans = 0
for i, j, k in permutations(d, 3):
    ans += min(i - 2, j - 4, k - 4) >= 0
ans //= 2
for i, j in permutations(d, 2):
    ans += min(i - 14, j - 4) >= 0
    ans += min(i - 2, j - 24) >= 0
for i in d:
    ans += i - 74 >= 0
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
def sieve(n):
    if n <= 4:
        return list(range(2, n))
    def _sieve_of_eratosthenes(n):
        limit = int(sqrt(n))+1
        *table, = [1] * n
        table[0] = table[1] = 0
        for i in range(2, limit):
            if table[i]:
                for j in range(i**2, n, i):
                    table[j] = 0
        return [i for i in range(2, n) if table[i]]
    return _sieve_of_eratosthenes(n)

def factorint(n):
    d = {}
    for i in range(2, int(sqrt(n))+1):
        c = 0
        q, r = divmod(n, i)
        while not r:
            c += 1
            n = q
            q, r = divmod(n, i)
        if c:
            d[i] = c
    if n != 1:
        d[n] = 1
    return d

n = int(input())
P = sieve(n+1)
d = {p:i for i, p in enumerate(P)}
X = [1] * len(P)
for i in range(2, n+1):
    for k, v in factorint(i).items():
        X[d[k]] += v
nb_3 = len([x for x in X if x >= 3])
nb_5 = len([x for x in X if x >= 5])
nb_15 = len([x for x in X if x >= 15])
nb_25 = len([x for x in X if x >= 25])
nb_75 = len([x for x in X if x >= 75])
print(nb_75 + nb_25*(nb_3-1) + nb_15*(nb_5-1) + nb_5*(nb_5-1)*(nb_3-2)//2)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())

dp = [0] * (N + 1)

for i in range(1, N + 1):
    x = i
    for j in range(2, i):
        while x % j == 0:
            x //= j
            dp[j] += 1
    if x != 1:
        dp[x] += 1
# dp = sorted(dp, reverse=True)

ans = 0
ans += any(x for x in dp if x >= 74)

x = 0
y = 0
for i in range(N + 1):
    if dp[i] >= 24:
        x += 1
    if dp[i] >= 2:
        y += 1
ans += x * (y - 1)

x = 0
y = 0
for i in range(N + 1):
    if dp[i] >= 14:
        x += 1
    if dp[i] >= 4:
        y += 1
ans += x * (y - 1)

x = 0
y = 0
z = 0
for i in range(N + 1):
    if dp[i] >= 4:
        x += 1
        y += 1
    if dp[i] >= 2:
        z += 1
ans += x * (y - 1) * (z - 2) // 2
# print(dp)
# print(x, y, z)

print(ans)

Submission status: Accepted

Solution code:
def prime_factors(n):
    i = 2
    factors = []
    while i**2 <= n:
        if n % i != 0:
            i += 1
        else:
            factors.append(i)
            n = n // i
    if n > 1:
        factors.append(n)
    return factors

def resolve():
    N = int(input())
    factors = []
    for i in range(1, N+1):
        factors.extend(prime_factors(i))
    import collections
    cnter = collections.Counter(factors)
    
    n_over_74 = 0
    n_over_24 = 0
    n_over_14 = 0
    n_over_4 = 0
    n_over_2 = 0
    for k, cnt in cnter.items():
        if cnt >= 74:
            n_over_74 += 1
        if cnt >= 24:
            n_over_24 += 1
        if cnt >= 14:
            n_over_14 += 1
        if cnt >= 4:
            n_over_4 += 1
        if cnt >= 2:
            n_over_2 += 1
    
    ans = 0
    if n_over_74 >= 1:
        ans += n_over_74
    if n_over_4 >= 1 and n_over_14 >= 1:
        ans += n_over_14*(n_over_4-1)
    if n_over_24 >= 1 and n_over_2 >= 1:
        ans += n_over_24*(n_over_2-1)
    if n_over_4 >= 2 and n_over_2 >= 3:
        ans += int((n_over_4*(n_over_4-1)/2)*(n_over_2-2))
    print(ans)

    
        

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())

factor_list = defaultdict(int)
for i in range(1, n+1):
    p = 2
    t = i
    while p <= n**0.5+5:
        if t%p == 0:
            factor_list[p] += 1
            t //= p
        else:
            p += 1
    if t > 1:
        factor_list[t] += 1

nums = [0 for _ in range(1000)]

for k, v in factor_list.items():
    nums[v] += 1

for i in range(998, -1, -1):
    nums[i] += nums[i+1]

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

Submission status: Accepted

Solution code:
n = int(input())
if n==1:
    print(0)
    exit(0)
primes = [True]*(n+1)
primes[0] = False
primes[1] = False
for i in range(2, n+1):
    if primes[i]:
        for j in range(i*2, n+1, i):
            primes[j] = False
primes = [i for i, j in enumerate(primes) if j]
factors = {2:0, 4:0, 14:0, 24:0, 74:0}
for i in primes:
    tmp = 0
    j = i
    while j<=n:
        tmp += n//j
        j *= i
    for k in factors:
        if tmp>=k:
            factors[k] += 1
ans = factors[4]*(factors[4]-1)*(factors[2]-2)//2
ans += factors[14]*(factors[4]-1)
ans += factors[24]*(factors[2]-1)
ans += factors[74]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))

def factorization(n):
    #arr = []
    #arr = defaultdict(int)
    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])
            arr[i] += cnt

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

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

    return arr

N =ii()
arr = defaultdict(int)

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

cnt = [0]*100

for key, value in arr.items():
    cnt[1] += 1
    cnt[value+1] += -1

cnt = list(accumulate(cnt))

ans = 0
#print(arr)
#print(cnt)
if cnt[4] > 1:
    #ans += cnt[4] * (cnt[2]-1) * (cnt[2]-2) // 2
    #ans += (cnt[2]-1) * (cnt[2]-2) // 2
    #ans = cnt[2] * (cnt[2]-1) // 2
    #ans += (cnt[2]-2)
    #ans += cnt[4] * (cnt[4]-1) // 2 * (cnt[2]-cnt[4])
    #ans += cnt[4] * (cnt[4]-1) * (cnt[4]-2) // 6
    ans += cnt[4] * (cnt[4]-1) // 2 * (cnt[2]-2)

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

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:
# coding: utf-8

# https://atcoder.jp/contests/abc114
# 14:44-15:24 done


def soinsubunkai(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


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

    soinsu = {}
    for i in range(2, N+1):
        i_soinsu = soinsubunkai(i)
        for p, idx in i_soinsu:
            if p not in soinsu:
                soinsu[p] = idx
            else:
                soinsu[p] += idx

    n_75, n_25, n_15, n_5, n_3 = 0, 0, 0, 0, 0
    for v in soinsu.values():
        if v >= 74:
            n_75 += 1
        if v >= 24:
            n_25 += 1
        if v >= 14:
            n_15 += 1
        if v >= 4:
            n_5 += 1
        if v >= 2:
            n_3 += 1

    n_3_5_5 = n_5 * (n_5-1) * (n_3-2) // 2
    n_5_15 = n_15 * (n_5-1)
    n_3_25 = n_25 * (n_3-1)

    return n_3_5_5 + n_5_15 + n_3_25 + n_75


print(main())

Submission status: Accepted

Solution code:
def prime_factorization(n):
    for i in range(2, n + 1):
        num = int(i ** 0.5)
        for prime in range(2, num + 2):
            if i % prime == 0:
                cnt = 0
                while True:
                    if i % prime != 0: break
                    cnt += 1
                    i = i // prime
                if rec.get(prime):
                    rec[prime] += cnt
                else:
                    rec[prime] = cnt

        if i != 1:
            if rec.get(i):
                rec[i] += 1
            else:
                rec[i] = 1

n = int(input())
rec = dict()
prime_factorization(n)
dic = {2:0, 4:0, 14:0, 24:0, 74:0}
cnt = 0
for key, val in rec.items():
    if val >= 2:dic[2] += 1
    if val >= 4:dic[4] += 1
    if val >= 14:dic[14] += 1
    if val >= 24:dic[24] += 1
    if val >= 74:dic[74] += 1

for i in [74, 24, 14, 4]:
    temp = dic.get(i)
    if i == 74:cnt += temp
    elif i == 24:cnt += temp * (dic[2] - 1)
    elif i == 14:cnt += temp * (dic[4] - 1)
    else:cnt += (dic[2] - 2) * (temp - 1) * temp // 2
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict


def factorization(n):
    global ND
    temp = n
    flag = True
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            flag = False
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            ND[i] += cnt

    if temp!=1:
        ND[temp] +=1
        flag = False

    if flag:
        ND[n] += 1

    return


N = int(input())
ND = defaultdict(int)
for i in range(2, N+1):
    factorization(i)

L2 = 0
L4 = 0
L14 = 0
L24 = 0
L74 = 0

for key, value in ND.items():
    if value >= 2:
        L2 += 1
    if value >= 4:
        L4 += 1
    if value >= 14:
        L14 += 1
    if value >= 24:
        L24 += 1
    if value >= 74:
        L74 += 1

ans = 0
ans += L4 * (L4-1)//2 * (L2 - 2)
ans += L24 * (L2 - 1)
ans += L14 * (L4 - 1)
ans += L74
print(ans)

Submission status: Accepted

Solution code:
# 60 -> {2:2, 3:1, 5:1}
def factorization(n):
    pf_cnt = {}
    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
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1

    return pf_cnt


n = int(input())
prime_cnts = {}
for i in range(1,n+1):
    fac = factorization(i)
    for prime, cnt in fac.items():
        prime_cnts.setdefault(prime, 0)
        prime_cnts[prime] += cnt


cnt_74 = 0
cnt_24 = 0
cnt_14 = 0
cnt_4 = 0
cnt_2 = 0
for prime, cnt in prime_cnts.items():
    if cnt >= 74:
        cnt_74 += 1
    if cnt >= 24:
        cnt_24 += 1
    if cnt >= 14:
        cnt_14 += 1
    if cnt >= 4:
        cnt_4 += 1
    if cnt >= 2:
        cnt_2 += 1

ans = 0
ans += cnt_74
ans += cnt_14*(cnt_4-1)
ans += cnt_24*(cnt_2-1)
ans += (cnt_2-2) * cnt_4*(cnt_4-1)//2
print(ans)

Submission status: Accepted

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

def factorization(n):
    c = Counter()
    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
            c[i]=cnt
    if temp!=1:
        c[temp]=1
    if len(c)==0:
        c[n]=1
    c[1] = 0
    return c

def isOk(c):
    ret = 1
    for _,v in c.items():
        ret*=(v+1)
    return ret

c = Counter([])
for i in range(1, n+1):
    c += factorization(i)

# cから適当に約数を選んで約数の個数が75となるように選ぶ
# factorization(75): [5,2][3,1]
lc = [[k, v] for k, v in c.items()]

ans=0
# 一つの素因数が75個
f75 = sum([1 for v in c.values() if v >= 74])
ans+=f75
# 3, 3, 5のパターン
f3 = sum([1 for v in c.values() if v >= 2])
f5 = sum([1 for v in c.values() if v >= 4])
f15 = sum([1 for v in c.values() if v >= 14])
f25 = sum([1 for v in c.values() if v >= 24])
ans+=f15*(f5-1)
ans+=f25*(f3 - 1)
if f5 >= 2:
    ans+=(f5*(f5-1)//2)*(f3-2)
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
import numpy as np
n = int(input())
dic = defaultdict(lambda : 0)
for i in range(2, n + 1):
    sqrt = math.floor(i ** 0.5)
    for j in range(2, sqrt + 1):
        if not i % j:
            count = 0
            while i % j == 0:
                count += 1
                i //= j
            dic[j] += count
    if i > 1:
        dic[i] += 1
values = np.array(list(dic.values()))
v1 = len(values[values >= 2])
v2 = len(values[values >= 4])
v = (v2 * (v2 - 1) // 2) * (v1 - 2)

v3 = len(values[values >= 24])
v += v3 * (v1 - 1)

v4 = len(values[values >= 14])
v += v4 * (v2 - 1)

v5 = len(values[values >= 74])
v += v5
print(v)

Submission status: Accepted

Solution code:
N=int(input())



from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


from collections import defaultdict
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

count=1
D=defaultdict(int)
for i in range(1,N+1):
    f=factorization(i)
    for t in f:
        num,con=t
        D[num]+=con
threes=0
fives=0
num_15=0
num_25=0
num_75=0

for v in D.values():
    if v>=2:
        threes+=1
    if v>=4:
        fives+=1
    if v>=14:
        num_15+=1
    if v>=24:
        num_25+=1
    if v>=74:
        num_75+=1
#3*5*5
ans=(threes-fives)*fives*(fives-1)//2
if fives>=3:
    #ans+=cmb(fives, 3)
    ans+=fives*(fives-1)*(fives-2)//2
#75*1

ans+=num_75
#5*15

ans+=num_15*(fives-1)
#3*25
ans+=num_25*(threes-1)
print(ans)
#print(D)
#print(threes, fives, num_15, num_25, num_75)
#print(factorization(32400))

Submission status: Accepted

Solution code:
from collections import Counter

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

li = []

for i in range(1,n+1):
    li += prime_factorize(i)

C = Counter(li)

a,b,c,d,e = 0,0,0,0,0

for i in C.values():
    if i >= 74:
        e += 1
    elif i >= 24:
        d += 1
    elif i >= 14:
        c += 1
    elif i >= 4:
        b += 1
    elif i >= 2:
        a += 1

point = 0
point += e
point += (d+e)*(a+b+c) + (d+e)*(d+e-1)
point += (c+d+e)*b + (c+d+e)*(c+d+e-1)
point += a*((b+c+d+e)*(b+c+d+e-1)//2) + (b+c+d+e)*((b+c+d+e-1)*(b+c+d+e-2)//2)

print(point)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict

N = int(input())

# 素数のリスト
def createPrimeList(N, isTable=True):
    isPrime = [True] * (N + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, N):
        if not isPrime[i]:
            continue
        for p in range(i * 2, N, i):
            isPrime[p] = False
    return isPrime if isTable else [i for i in range(2, N) if isPrime[i]]

# 素因数分解(複数回)
primeList = createPrimeList(100, False)
def primeFactorization(N):
    primes = Counter()
    for p in primeList:
        while N % p == 0:
            N //= p
            primes[p] += 1
    return primes
primes = Counter()
for i in range(1, N + 1):
    primes += primeFactorization(i)

cnt = defaultdict(int)
for c in primes.values():
    c += 1
    for d in (3, 5, 15, 25, 75):
        if c >= d:
            cnt[d] += 1

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

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict

N = int(input())

def primeFactorization(N):
    primes = Counter()
    R = int(N**(0.5)) + 1
    for num in range(2, R):
        while N % num == 0:
            N //= num
            primes[num] += 1
    if N > 1 :
        primes[N] = 1
    return primes

primes = Counter()
for i in range(1, N + 1):
    primes += primeFactorization(i)

cnt = defaultdict(int)
for c in primes.values():
    c += 1
    for d in (3, 5, 15, 25, 75):
        if c >= d:
            cnt[d] += 1

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

Submission status: Accepted

Solution code:
P = [1 for _ in range(100)]
P[0]=0
P[1]=0
for i in range(2,11):
    for j in range(i*i,100,i):
        P[j] = 0
Q = []
for i in range(100):
    if P[i]==1:
        Q.append(i)
N = int(input())
C = {p:0 for p in Q}
for p in Q:
    cnt = 0
    k = 1
    while p**k<=N:
        for i in range(2,N+1):
            if i%(p**k)==0:
                cnt += 1
        k += 1
    C[p]=cnt
c2=0
c4=0
c14=0
c24=0
c74=0
for p in C:
    if C[p]>=2:
        c2 += 1
    if C[p]>=4:
        c4 += 1
    if C[p]>=14:
        c14 += 1
    if C[p]>=24:
        c24 += 1
    if C[p]>=74:
        c74 += 1
ans = ((c4*(c4-1))//2)*(c2-2)
ans += c24*(c2-1)
ans += c14*(c4-1)
ans += c74
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

def multiply_primes(a, b):
    """素因数分解系のCounter型のa, bに対してa*bの素因数分解系を計算する"""
    res = Counter([])
    keys = a.keys() | b.keys()
    for k in keys:
        res[k] = a[k] + b[k]
    return res

N = int(input())

# 答えは N! の約数かつ
# 素因数分解が x^2 y^4 z^4 の形になるもの
# 素因数分解が x^74 の形になるもの
# 素因数分解が x^2 y^24 の形になるもの
# 素因数分解が x^4 y^14 の形になるもの
# しかない

f = Counter([])  # f が N! の素因数分解になる
for n in range(2, N+1):
    f = multiply_primes(f, Counter(prime_factorize(n)))

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

for item in f.items():
    k = item[1]
    c2 += (k >= 2)
    c4 += (k >= 4)
    c14 += (k >= 14)
    c24 += (k >= 24)
    c74 += (k >= 74)

ans_2_4_4 = (c4 * (c4 - 1))//2 * (c2 - 2)
ans_74 = c74
ans_2_24 = c24 * (c2 - 1)
ans_4_14 = c14 * (c4 - 1)

ans = ans_2_4_4 + ans_74 + ans_2_24 + ans_4_14
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
 
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
from collections import defaultdict
d = defaultdict(int)
for i in range(2, n + 1):
    a = prime_factorize(i)
    for j in a:
        d[j] += 1
cnt_74 = []
cnt_2 = []
cnt_4 = []
cnt_14 = []
cnt_24 = []
for i in d:
    if d[i] >= 74:
        cnt_74.append(i)
    if d[i] >= 2:
        cnt_2.append(i)
    if d[i] >= 4:
        cnt_4.append(i)
    if d[i] >= 14:
        cnt_14.append(i)
    if d[i] >= 24:
        cnt_24.append(i)
ans = 0
ans += len(cnt_74)

for i in cnt_2:
    for j in cnt_24:
        if i != j:
            ans += 1
for i in cnt_4:
    for j in cnt_14:
        if i != j:
            ans += 1
for i in cnt_2:
    for j in range(len(cnt_4)):
        for k in range(j + 1, len(cnt_4)):
            j_ = cnt_4[j]
            k_ = cnt_4[k]
            if i != j_ and j_ != k_ and k_ != i:
                ans += 1
print(ans)
#print(d)

Submission status: Accepted

Solution code:
def prime_factorize(n):
    dic = {}
    while n % 2 == 0:
        if 2 in dic:
            dic[2] += 1
        else:
            dic[2] = 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f in dic:
                dic[f] += 1
            else:
                dic[f] = 1
            n //= f
        else:
            f += 2
    if n != 1:
        if n in dic:
            dic[n] += 1
        else:
            dic[n] = 1
    return dic

n = int(input())

dic = {}
for i in range(1, n+1):
    dici = prime_factorize(i)
    for key in dici:
        if key in dic:
            dic[key] += dici[key]
        else:
            dic[key] = dici[key]

num74 = 0
num24 = 0
num2 = 0
num4 = 0
num14 = 0
for key, value in dic.items():
    if value >= 74:
        num74 += 1
    if value >= 24:
        num24 += 1
    if value >= 2:
        num2 += 1
    if value >= 4:
        num4 += 1
    if value >= 14:
        num14 += 1
    
ans = num74 + num24*(num2-1) + (num4-1)*num14 + (num2-2)*(num4*(num4-1)//2)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
m=[0]*101
for i in range(1,n+1):
  for j in range(2,n+1):
    while i%j==0:
      a=i//j
      while (a+1)*j<=i:
        a+=1
      i=a
      m[j]+=1
counter75=0
counter25=0
counter15=0
counter5=0
counter3=0
for i in range(101):
  if m[i]>=74:
    counter75+=1
  if m[i]>=24:
    counter25+=1
  if m[i]>=14:
    counter15+=1
  if m[i]>=4:
    counter5+=1
  if m[i]>=2:
    counter3+=1
a=(counter5*(counter5-1)*(counter3-2))//2
while (a+1)*2<=(counter5*(counter5-1)*(counter3-2)):
  a+=1
print(counter75+counter25*(counter3-1)+counter15*(counter5-1)+a)

Submission status: Accepted

Solution code:
##昨日やった...
import numpy as np

def prime_factorize(N): #素因数分解
    exponent = 0
    while N%2 == 0:
        exponent += 1
        N //= 2
    if exponent: factorization = [[2,exponent]]
    else: factorization = []
    i=1
    while i*i <=N:
        i += 2
        if N%i: continue
        exponent = 0
        while N%i == 0:
            exponent += 1
            N //= i
        factorization.append([i,exponent])
    if N!= 1: factorization.append([N,1])
    assert N != 0, "zero"
    return factorization

factors = [0]*100
N = int(input())

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

factors = np.array(factors)
ov2 = len(factors[factors >= 2])
ov4 = len(factors[factors >= 4])
ov14 = len(factors[factors >= 14])
ov24 = len(factors[factors >= 24])
ov74 = len(factors[factors >= 74])
ans = 0
## 2*4*4
ans += (ov4-2)*(ov4)*(ov4-1)//2 + (ov2-ov4)*(ov4)*(ov4-1)//2

## 14 * 4
ans += (ov4-ov14)*(ov14) + (ov14)*(ov14-1)

## 24 * 2
ans += (ov2-ov24)*ov24 + (ov24)*(ov24-1)

## 74
ans += ov74

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

def solve():
    input = sys.stdin.readline
    N = int(input())
    primes = defaultdict(int)
    ans = 0
    for i in range(1, N + 1):
        k = i
        for j in range(2, i+1):
            if j ** 2 > i: break
            if k % j == 0:
                while k % j == 0:
                    primes[j] += 1
                    k //= j
        if k > 1: primes[k] += 1
    P = []
    for key in primes: P.append(primes[key])
    pn = len(P)

    for i in range(pn):
        if P[i] >= 74: ans += 1
        if P[i] >= 24:
            for j in range(pn):
                if P[j] >= 2 and j != i: ans += 1
        if P[i] >= 14:
            for j in range(pn):
                if P[j] >= 4 and j != i: ans += 1
        if P[i] >= 4:
            for j in range(i+1, pn):
                if P[j] >= 4:
                    for k in range(pn):
                        if P[k] >= 2 and k != i and k != j: ans += 1
    print(ans)
    #print(primes)
    #print(P)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict

N = int(input())

# 素数のリスト
def createPrimeList(N, isTable=True):
    isPrime = [True] * N
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, N):
        if not isPrime[i]:
            continue
        for p in range(i * 2, N, i):
            isPrime[p] = False
    return isPrime if isTable else [i for i in range(2, N) if isPrime[i]]

# 素因数分解(複数回)
isPrime = createPrimeList(10**5, False)
def primeFactorization(N):
    primes = Counter()
    for p in isPrime:
        while N % p == 0:
            N //= p
            primes[p] += 1
    return primes

primes = Counter()
for i in range(1, N + 1):
    primes += primeFactorization(i)

cnt = defaultdict(int)
for c in primes.values():
    c += 1
    for d in (3, 5, 15, 25, 75):
        if c >= d:
            cnt[d] += 1

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

Submission status: Accepted

Solution code:
n=int(input())
ans=0
temp=[0]*101

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
  
for i in range(1,n+1):
  a=factorization(i)
  for j in range(len(a)):
    temp[a[j][0]]=temp[a[j][0]]+a[j][1]
t75=0
t25=0
t15=0
t5=0
t3=0
t1=0
for i in range(n):
  if temp[i]>=74:
    t75=t75+1
  if temp[i]>=24:
    t25=t25+1
  if temp[i]>=14:
    t15=t15+1
  if temp[i]>=4:
    t5=t5+1
  if temp[i]>=2:
    t3=t3+1
  if temp[i]>=1:
    t1=t1+1
print(t75+t25*(t3-1)+t15*(t5-1)+t5*(t5-1)*(t3-2)//2)

Submission status: Accepted

Solution code:
from collections import defaultdict
import itertools

def pfact(m):
	pf = {}
	for i in range(2,int(m**0.5)+1):
		while m%i == 0:
			pf[i] = pf.get(i,0) + 1
			m //= i
	if m>1 : pf[m]=1
	return pf

n = int(input())

plist = defaultdict(lambda: 0)
for i in range(2, n+1):
	for j, k in pfact(i).items():
		plist[j] += k

def makediv(n):
	lower_divisors , upper_divisors = [], []
	i = 1
	while i*i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n//i)
		i += 1
	return lower_divisors + upper_divisors[::-1]

shichigo = set(makediv(75))
shichigo.remove(1)

thelist = [j+1 for j in plist.values()]
thelist.sort()

ansdict = {
	3: 0,
	5: 0,
	15: 0,
	25: 0,
	75: 0
}

for cnt, i in enumerate(thelist):
	for j in range(i+1):
		if j in shichigo:
			ansdict[j] += 1

"""
75
= 5*15
= 3*25
= 3*5*5
"""

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

Submission status: Accepted

Solution code:
import math
N = int(input())


def trial_division(n):
    # 2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            primes[num] += 1
    # リストが空ならそれは素数
    if n != 1:
        primes[n] += 1
        return


primes = [0 for _ in range(N+1)]
for i in range(2, N+1):
    trial_division(i)

P74, P24, P14, P4, P2 = 0, 0, 0, 0, 0
for i in range(2, N+1):
    if primes[i] >= 74:
        P74 += 1
    if primes[i] >= 24:
        P24 += 1
    if primes[i] >= 14:
        P14 += 1
    if primes[i] >= 4:
        P4 += 1
    if primes[i] >= 2:
        P2 += 1

ans = 0
ans += P4*(P4-1)//2*(P2-2)
ans += P14*(P4-1)
ans += P24*(P2-1)
ans += P74
print(ans)

Submission status: Accepted

Solution code:
from math import factorial


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


n = int(input())
f = [0] * 101
for p in factorize(factorial(n)):
    f[p] += 1
cnt24 = 0
cnt14 = 0
cnt4 = 0
ans = 0
tmp = 0
for i in range(1, n + 1):
    if f[i] >= 74:
        ans += 1
    for j in range(1, n + 1):
        if i == j:
            continue
        if f[i] >= 24 and f[j] >= 2:
            ans += 1
        if f[i] >= 14 and f[j] >= 4:
            ans += 1
        for k in range(1, n + 1):
            if i == k or j == k:
                continue
            if f[i] >= 4 and f[j] >= 4 and f[k] >= 2:
                tmp += 1
print(ans + tmp // 2)