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:
def calc(N,p):
  ans = 0
  i = p
  while N>=i:
    ans += N//i
    i *= p
  return ans

def sieve(n):
  is_prime = [True for _ in range(n+1)]
  is_prime[0] = False
  for i in range(2, n+1):
    if is_prime[i-1]:
      j = 2 * i
      while j <= n:
        is_prime[j-1] = False
        j += i
  table = [i for i in range(1, n+1) if is_prime[i-1]]
  return table
  
from itertools import groupby, accumulate, product, permutations, combinations
def check(value,lis):
  ans = 0
  n = len(lis)
  for perm in permutations(value,n):
    for i in range(n):
      if perm[i]<lis[i]:
        break
    else:
      ans += 1
  return ans

def solve():
  N = int(input())
  table = sieve(N)
  v = []
  for p in table:
    v.append(calc(N,p))
  v.sort(reverse=True)
  ans = 0
  ans += check(v,[74])
  ans += check(v,[24,2])
  ans += check(v,[14,4])
  ans += check(v,[4,4,2])//2
  return ans
print(solve())

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import chain


def prime_set(N):
    """
    Nまでの素数のsetを返す
    """
    if N < 4:
        return ({}, {}, {2}, {2, 3})[N]
    Nsq = int(N ** 0.5 + 0.5) + 1
    primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
    for i in range(5, Nsq, 2):
        if i in primes:
            primes -= set(range(i * i, N + 1, i * 2))
    return primes


def prime_factorization(n):  # 素因数分解
    res = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            res.append((i, cnt))
    if n > 1:
        res.append((n, 1))
    return res


N = int(input())
primes = {p: 0 for p in prime_set(100)}
for i in range(2, N + 1):
    pf = prime_factorization(i)
    for p, f in pf:
        primes[p] += f


n2 = n4 = n14 = n24 = n74 = 0
for v in primes.values():
    if v >= 74:
        n74 += 1
    if v >= 24:
        n24 += 1
    if v >= 14:
        n14 += 1
    if v >= 4:
        n4 += 1
    if v >= 2:
        n2 += 1

ans = 0
if n74:
    ans += n74
if n24:
    ans += n24 * (n2 - 1)
if n14:
    ans += n14 * (n4 - 1)
if n4 >= 2 and n2:
    ans += n4 * (n4 - 1) // 2 * (n2 - 2)

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**2,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 i in range(2,N+1):
    for p in Q:
        if i%p==0:
            x = i
            while x%p==0:
                x = x//p
                C[p] += 1
cnt = 0
for p in Q:
    if C[p]>=74:
        cnt += 1
cnt1 = 0
cnt2 = 0
for p in Q:
    if C[p]>=24:
        cnt2 += 1
    elif C[p]>=2:
        cnt1 += 1
cnt += cnt2*(cnt2-1)+cnt2*cnt1
cnt1 = 0
cnt2 = 0
for p in Q:
    if C[p]>=14:
        cnt2 += 1
    elif C[p]>=4:
        cnt1 += 1
cnt += cnt2*(cnt2-1)+cnt2*cnt1
cnt1 = 0
cnt2 = 0
for p in Q:
    if C[p]>=4:
        cnt2 += 1
    elif C[p]>=2:
        cnt1 += 1
cnt += (cnt2*(cnt2-1)*(cnt2-2))//2+((cnt2*(cnt2-1))//2)*cnt1
print(cnt)

Submission status: Accepted

Solution code:

# 75 = 5 * 5 * 3
# 3 * 5 * 5, 3 * 25, 5 * 15, 75


n = int(input())

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

i3 = i5 = i15 = i25 = i75 = 0
for _, v in enumerate(div):
    if v >= 74:
        i75 += 1
    if v >= 24:
        i25 += 1
    if v >= 14:
        i15 += 1
    if v >= 4:
        i5 += 1
    if v >= 2:
        i3 += 1
ans = i75
ans += i25 * (i3 - 1)
ans += i15 * (i5 - 1)
ans += (i5 - 1) * i5 // 2 * (i3 - 2)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import combinations, permutations


def factor(n):
    res = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            res.append(i)
            n //= i
    if n > 1:
        return res + [n]
    else:
        return res


N = int(input())
if N < 10:
    print(0)
    exit()

cnt = Counter()
for i in range(2, N + 1):
    primes = factor(i)
    cnt += Counter(primes)

ans = 0
for x, y in combinations(cnt, 2):
    if cnt[x] < 4 or cnt[y] < 4:
        continue
    for z in cnt:
        if z == x or z == y or cnt[z] < 2:
            continue
        ans += 1

for x, y in permutations(cnt, 2):
    if cnt[x] >= 14 and cnt[y] >= 4:
        ans += 1

for x, y in permutations(cnt, 2):
    if cnt[x] >= 24 and cnt[y] >= 2:
        ans += 1

for x in cnt:
    if cnt[x] >= 74:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

import math
def factorize(n):
    d = {}
    temp = int(math.sqrt(n))+1
    for i in range(2, temp):
        while n%i== 0:
            n //= i
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
    if d == {}:
        d[n] = 1
    else:
        if n in d:
            d[n] += 1
        elif n != 1:
            d[n] =1
    return d

D = {}
for i in range(1, n+1):
    d = factorize(i)
    for k, v in d.items():
        if k in D:
            D[k] += v
        else:
            D[k] = v
#print(D)
p74 = 0
p24 = 0
p14 = 0
p4 = 0
p2 = 0
for k, v in D.items():
    if v >= 74:
        p74 += 1
        p24 += 1
        p14 += 1
        p4 +=1
        p2 +=1
    elif v >= 24:
        p24 += 1
        p14 += 1
        p4 +=1
        p2 +=1
    elif v >= 14:
        p14 += 1
        p4 +=1
        p2 +=1
    elif v >= 4:
        p4 +=1
        p2 +=1
    elif v >= 2:
        p2 +=1
    else:
        pass

ans = 0
# 3*5*5
ans += (p4*(p4-1)//2)*(p2-2)
# 3*25
ans += p24*(p2-1)
# 5*15
ans += p14*(p4-1)
# 75
ans += p74
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

fac = Counter()
for n in range(1,N+1):
    fac += factorize(n)

ans = 0
v4 = v2 = 0
for v in fac.values():
    if v >= 4:
        v4 += 1
    elif v >= 2:
        v2 += 1
t = v4 * (v4-1)//2 * (v4-2+v2)
if t > 0:
    ans += t

v24 = v2 = 0
for v in fac.values():
    if v >= 24:
        v24 += 1
    elif v >= 2:
        v2 += 1
t = v24 * (v24-1+v2)
ans += t

v14 = v4 = 0
for v in fac.values():
    if v >= 14:
        v14 += 1
    elif v >= 4:
        v4 += 1
t = v14 * (v14-1+v4)
ans += t

v74 = 0
for v in fac.values():
    if v >= 74:
        v74 += 1
ans += v74

print(ans)

Submission status: Accepted

Solution code:
def p_factorization(n):
    if n == 1: return {}
    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
    return pf_cnt


n = int(input())
pd = {}
for i in range(1,n+1):
    curr_p = p_factorization(i)
    for p,cnt in curr_p.items():
        pd.setdefault(p,0)
        pd[p] += cnt

ans = 0

cnt3 = 0
cnt5 = 0
cnt15 = 0
cnt25 = 0
cnt75 = 0

for v in pd.values():
    if v >= 74: cnt75 += 1
    if v >= 24: cnt25 += 1
    if v >= 14: cnt15 += 1
    if v >= 4: cnt5 += 1
    if v >= 2: cnt3 += 1


ans += cnt75
ans += max(cnt15*(cnt5-1), 0)
ans += max(0,cnt25*(cnt3-1))
ans += max(0,(cnt3-2)*(cnt5)*(cnt5-1)//2)
print(ans)

Submission status: Accepted

Solution code:
import sys
primes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
num3=0
num5=0
num15=0
num25=0
num75=0
n=int(input())
for i in primes:
  tmp=0
  j=1
  while n//pow(i,j)>0:
    tmp+=n//pow(i,j)
    j+=1
  if tmp>=2:
    num3+=1
  if tmp>=4:
    num5+=1
  if tmp>=14:
    num15+=1
  if tmp>=24:
    num25+=1
  if tmp>=74:
    num75+=1
print(num75+max(0,(num3-1)*num25)+max(0,((num3-2)*(num5-1)*num5)//2)+max(0,((num5-1)*num15)))

Submission status: Accepted

Solution code:
def prime_factorize(N,lis):
    a = []
    n = N
    while n % 2 == 0:
        lis[2] += 1
        n //= 2
    f = 3
    while f * f <= N:
        if n % f == 0:
            lis[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        lis[n] += 1

N = int(input())
lis = [0] * 101
for i in range(1,N+1):
    prime_factorize(i,lis)
d = [0] * 100
for i in lis:
    d[i] += 1
for i in reversed(range(len(d)-1)):
    d[i] += d[i+1]

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

Submission status: Accepted

Solution code:
def prime_factorize(N,lis):
    a = []
    n = N
    while n % 2 == 0:
        lis[2] += 1
        n //= 2
    f = 3
    while f * f <= N:
        if n % f == 0:
            lis[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        lis[n] += 1

N = int(input())
lis = [0] * 101
for i in range(1,N+1):
    prime_factorize(i,lis)
#print(lis)
lis.sort()
ans = 0
for i in range(101):
    for j in range(i+1,101):
        for k in range(j+1,101):
            if lis[i] >= 2 and lis[j] >= 4:
                ans += 1
            if lis[i] >= 4:
                ans += 2
for i in range(101):
    for j in range(i+1,101):
        if lis[i] >= 4 and lis[j] >= 14:
            ans += 1
            if lis[i] >= 14:
                ans += 1
        if lis[i] >= 2 and lis[j] >= 24:
            ans += 1
            if lis[i] >= 24:
                ans += 1
for i in range(101):
    if lis[i] >= 74:
        ans += 1
print(ans)

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())
cnt = [0]*101
ans=0

for i in range(1,n+1):
  lst = factorization(i)
  for j in lst:
    cnt[j[0]]+=j[1]

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

for i in cnt:
  if 2<=i<=3:
    a+=1
  elif 4<=i<=13:
    b+=1
  elif 14<=i<=23:
    c+=1
  elif 24<=i<=73:
    d+=1
  elif 74<=i:
    e+=1


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


print(ans)

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())
alist=[0]*101
for i in range(2,n+1):
  for j in factorization(i):
    alist[j[0]]+=j[1]
if n==1:
  print(0)
else:
  ans=0
  for i in range(1,100):
    if alist[i]>=74:
      ans+=1
    if alist[i]>=24:
      for j in range(1,100):
        if i!=j and alist[j]>=2:
          ans+=1
    if alist[i]>=14:
      for j in range(1,100):
        if i!=j and alist[j]>=4:
          ans+=1
    if alist[i]>=2:
      for j in range(1,100):
        for k in range(j+1,100):
          if i!=j and  k!=i and alist[j]>=4 and alist[k]>=4:
            ans+=1
  print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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


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

    prime = Counter()
    for n in range(1, N + 1):
        prime.update(prime_factorize(n))

    C = [0] * 101
    for v in prime.values():
        C[v] += 1

    for i in range(99, -1, -1):
        C[i] += C[i + 1]

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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


def com(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    r = min(r, n - r)
    numer = denom = 1
    for i in range(n - r + 1, n + 1):
        numer = numer * i
    for i in range(1, r + 1):
        denom = denom * i
    return numer // denom


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

    prime = Counter()
    for n in range(1, N + 1):
        prime.update(prime_factorize(n))

    C = [0] * 101
    for v in prime.values():
        C[v] += 1

    for i in range(99, -1, -1):
        C[i] += C[i + 1]

    ans = 0
    ans += (C[2] - 2) * com(C[4], 2)
    ans += (C[2] - 1) * C[24]
    ans += (C[4] - 1) * C[14]
    ans += C[74]

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
d = 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)
    return a

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

#print(d)



e = defaultdict(int)

l = [2, 4, 14, 24, 74]

#74
for k, v in d.items():
    for x in l:
        if v >= x:
            e[x] += 1

#print(e)

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline


def calc_prime_factors(n, count=False):
    """Trial division"""
    factors = []
    # factor: 2
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    # factor: 3, 5, 7, 11, ...
    f = 3
    root_n = int(n ** 0.5) + 1
    while f <= root_n:
        if n % f == 0:
            factors.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        factors.append(n)
    return factors


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

    n_factor = defaultdict(int)
    for n in range(1, N + 1):
        factors = calc_prime_factors(n)
        for f in factors:
            n_factor[f] += 1

    n_factor = list(n_factor.values())
    n_factor.sort()
    ans = 0

    # 75 = 3 x 3 x 5 : (2, 4, 4)
    A, B = 0, 0
    for n in n_factor:
        if 2 <= n <= 3:
            A += 1
        elif 4 <= n:
            B += 1
    ans += A * B * (B - 1) // 2 + B * (B - 1) * (B - 2) // 6 * 3

    # 75 = 3 x 25 : (2, 24)
    A, B = 0, 0
    for n in n_factor:
        if 2 <= n <= 23:
            A += 1
        elif 24 <= n:
            B += 1
    ans += A * B + B * (B - 1)

    # 75 = 5 x 15 : (4, 14)
    A, B = 0, 0
    for n in n_factor:
        if 4 <= n <= 13:
            A += 1
        elif 14 <= n:
            B += 1
    ans += A * B + B * (B - 1)

    # 75 = 75 : (74,)
    A = 0
    for n in n_factor:
        if 74 <= n:
            A += 1
    ans += A

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    n = int(input())
    fact = defaultdict(int)
    for i in range(2, n + 1):
        j = i
        while j % 2 == 0:
            j //= 2
            fact[2] += 1
        k = 3
        while k * k <= j:
            if j % k:
                k += 2
            else:
                j //= k
                fact[k] += 1
        if j != 1:
            fact[j] += 1
    fact = list(fact.items())
    length = len(fact)
    ans = 0
    for i in range(length):
        if fact[i][1] >= 74:
            ans += 1
    product = set()
    for small_p, large_p in [[2, 24], [4, 14]]:
        for i in range(length):
            for j in range(length):
                if i == j:
                    continue
                now = pow(fact[i][0], large_p) * pow(fact[j][0], small_p)
                if fact[i][1] >= large_p and fact[j][1] >= small_p and now not in product:
                    ans += 1
                    product.add(now)
    for i in range(length):
        for j in range(length):
            for k in range(length):
                if i == j or j == k or i == k:
                    continue
                now = pow(fact[i][0], 4) * pow(fact[j][0], 4) * pow(fact[k][0], 2)
                if fact[i][1] >= 4 and fact[j][1] >= 4 and fact[k][1] >= 2 and now not in product:
                    ans += 1
                    product.add(now)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def primesbelow(N):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    #""" Input N>=6, Returns a list of primes, 2 <= p < N """
    correction = N % 6 > 1
    N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
    sieve = [True] * (N // 3)
    sieve[0] = False
    for i in range(int(N ** .5) // 3 + 1):
        if sieve[i]:
            k = (3 * i + 1) | 1
            sieve[k*k // 3::2*k] = [False] * ((N//6 - (k*k)//6 - 1)//k + 1)
            sieve[(k*k + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1)
    return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]]

n=int(input())
primes=primesbelow(n+10)
factor={}

def val(n,d):
    ans=0
    t=d
    while(t<=n):
        ans+=(n//t)
        t*=d
    return ans
g2=0
g4=0
g24=0
g14=0
g74=0
for i in primes:
    k=val(n,i)
    if k>=4:
        g4+=1
    if k>=2:
        g2+=1
    if k>=24:
        g24+=1
    if k>=14:
        g14+=1
    if k>=74:
        g74+=1

a=(g2-2)*((g4*(g4-1))//2)
b=g24*(g2-1)
c=g14*(g4-1)
d=g74
print(a+b+c+d)

Submission status: Accepted

Solution code:
P = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
S = [0]*25

N = int(input())
for i in range(2, N+1):
    num = i
    j = 0
    while num > 1:
        if num%P[j] == 0:
            num //= P[j]
            S[j] += 1
        else:
            j += 1
            if j == 25:
                break

# 74
# 2 24
# 4 14
# 2 4 4

ans = 0
if S[0] >= 74:
    ans += 1
for i in range(3):
    if S[i] >= 24:
        tmp = -1
        for num in S:
            if num >= 2:
                tmp += 1
        ans += tmp
for i in range(4):
    if S[i] >= 14:
        tmp = -1
        for num in S:
            if num >= 4:
                tmp += 1
        ans += tmp
tmp4 = 0
tmp2 = 0
for num in S:
    if num >= 4:
        tmp4 += 1
    if num >= 2 and num < 4:
        tmp2 += 1
ans += tmp4*(tmp4-1)*(tmp4+tmp2-2)//2
print(ans)

Submission status: Accepted

Solution code:
"""
75数の条件
約数の個数は各素因数の個数a1,a2,a3,...について
(a1+1)(a2+1)...(an+1)
75=3*5*5
->素因数の個数が2個, 4個, 4個になるような組み合わせ
(2,4,4)
(14,4)
(2,24)
(74)

求め方
1〜Nについて、素因数の数をdictに収めていく
->そのうち、4個以上あるものの組み合わせと2個以上あるものの組み合わせでカウントする
"""
import copy
N=int(input())
sosu=[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]
soinsu=dict()
for n in range(2,N+1):
  if n in sosu:
    soinsu[n]=1
  else:
    x = copy.deepcopy(n)
    i = 0
    while i<len(sosu):
      if x % sosu[i]==0:
        soinsu[sosu[i]]+=1
        x = x//sosu[i]
      else:
        i += 1

ans = 0
cnt=[0,0,0,0,0]
tit=[2,4,14,24,74]
for _,v in soinsu.items():
  for i in range(5):
    cnt[i] += 1 if v >= tit[i] else 0

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

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import copy

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    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 = ni()
    divisor = [0 for _ in range(101)]

    ans = 0
    for i in range(1, n + 1):
        a = prime_factorize(i)
        for ai in a:
            divisor[ai] += 1

    over75 = 0
    over25 = 0
    over15 = 0
    over5 = 0
    over3 = 0
    for di in divisor:
        tmp = di + 1
        if tmp >= 75:
            over75 += 1
        if tmp >= 25:
            over25 += 1
        if tmp >= 15:
            over15 += 1
        if tmp >= 5:
            over5 += 1
        if tmp >= 3:
            over3 += 1

    ans = over75 + over25 * (over3 - 1) + over15 * (over5 - 1) + over5 * (over5 - 1) // 2 * (over3 - 2)

    print(ans)


if __name__ == '__main__':
    main()

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

ov74, ov24, ov14, ov4, ov2 = 0, 0, 0, 0, 0

for v in cnt.values():
    if v>=74:
        ov74 += 1
    
    if v>=24:
        ov24 += 1
        
    if v>=14:
        ov14 += 1
    
    if v>=4:
        ov4 += 1
    
    if v>=2:
        ov2 += 1

ans = ov74+ov24*(ov2-1)+ov14*(ov4-1)+ov4*(ov4-1)//2*(ov2-2)
print(ans)

Submission status: Accepted

Solution code:
import collections

n = int(input())

div = []

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

c = collections.Counter(div)
    
n2,n4,n14,n24,n74 = 0,0,0,0,0

for k,v in c.items():
    if v >= 2:
        n2 += 1
    if v >= 4:
        n4 += 1
    if v >= 14:
        n14 += 1
    if v >= 24:
        n24 += 1
    if v >= 74:
        n74 += 1

ans = n74 + n24*(n2-1) + n14*(n4-1) + n4*(n4-1)*(n2-2)//2

print(ans)

Submission status: Accepted

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

def division(n):
    if n < 2:
        return []
    
    prime_factors = []
    
    for i in range(2,int(n**0.5)+1):
        while n % i == 0:
            prime_factors.append(i)
            n //= i
    if n > 1:
        prime_factors.append(n)
        
    return prime_factors

num = []

for i in range(1,n+1):
    div = division(i)
    num.extend(div)
c = collections.Counter(num)

div_num = 1

n2, n4, n14, n24, n74 = 0,0,0,0,0

for k,v in c.items():
    if 2<=v:
        n2 += 1
    if 4<=v:
        n4 += 1
    if 14<=v:
        n14 += 1
    if 24<=v:
        n24 += 1
    if 74<=v:
        n74 += 1

ans = n74 + n24*(n2-1) + n14*(n4-1) + n4*(n4-1)*(n2-2)//2

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from copy import deepcopy

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())
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]
dp = [[0] * 26 for _ in range(N)]
if N == 1:
    print(0)
else:
    for i in range(1,N):
        dp[i] = deepcopy(dp[i-1])
        temp = Counter(prime_factorize(i+1))
        for x in temp.items():
            if len(prime_factorize(x[0])) == 1:
                dp[i][prime.index(x[0])] += x[1]
        four = 0
        two = 0
        fourteen = 0
        twenty_four = 0
        seventy_four = 0
        for j in range(25):
            if dp[i][j] >= 74:
                seventy_four += 1
                twenty_four += 1
                fourteen += 1
                four += 1
                two += 1
            elif dp[i][j] >= 24:
                twenty_four += 1
                fourteen += 1
                four += 1
                two += 1
            elif dp[i][j] >= 14:
                fourteen += 1
                four += 1
                two += 1
            elif dp[i][j] >= 4:
                four += 1
                two += 1
            elif dp[i][j] >= 2:
                two += 1
        dp[i][25] = ((four*(four-1))//2) * (two-2) + twenty_four * (two-1) + fourteen * (four-1) + seventy_four
    print(dp[N-1][25])

Submission status: Accepted

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


def sieve(n):
    n += 1
    res = [i for i in range(n)]
    for p in range(2, int(n**.5)+1):
        if res[p] < p:
            continue
        for q in range(p**2, n, p):
            if res[q] == q:
                res[q] = p
    return res


U = 100
min_factor = sieve(U)


def prime_factor(n):
    res = defaultdict(int)
    while 1 < n:
        res[min_factor[n]] += 1
        n //= min_factor[n]
    return res


cnt = defaultdict(int)
for i in range(1, n+1):
    for k, v in prime_factor(i).items():
        cnt[k] += v

facts = cnt.keys()
ans = 0
# 3,5,5
for subset in combinations(facts, 3):
    for i in range(3):
        can_be = 1
        for j, prim in enumerate(subset):
            if i == j:
                if cnt[prim] < 2:
                    can_be = 0
                    break
            else:
                if cnt[prim] < 4:
                    can_be = 0
                    break
        if can_be:
            ans += 1

# 15,5 3,25
for subset in combinations(facts, 2):
    for i in range(2):
        can_be = 1
        for j, prim in enumerate(subset):
            if i == j:
                if cnt[prim] < 4:
                    can_be = 0
                    break
            else:
                if cnt[prim] < 14:
                    can_be = 0
                    break
        if can_be:
            ans += 1

        can_be2 = 1
        for j, prim in enumerate(subset):
            if i == j:
                if cnt[prim] < 2:
                    can_be2 = 0
                    break
            else:
                if cnt[prim] < 24:
                    can_be2 = 0
                    break
        if can_be2:
            ans += 1

# 74個の場合
if 74 <= cnt[2]:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(4, n + 1, 2):
        sieve[i] = 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i * 2):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        result.append((p, e))
    return result


N = int(input())

prime_table = make_prime_table(N)
d = {}
for i in range(2, N + 1):
    for p, e in prime_factorize(i):
        d.setdefault(p, 0)
        d[p] += e

# 75 = 5 * 5 * 3
#    = 15 * 5
#    = 25 * 3
#    = 75
n74 = 0
n24 = 0
n14 = 0
n4 = 0
n2 = 0
for k in d:
    if d[k] >= 74:
        n74 += 1
    if d[k] >= 24:
        n24 += 1
    if d[k] >= 14:
        n14 += 1
    if d[k] >= 4:
        n4 += 1
    if d[k] >= 2:
        n2 += 1

result = 0
# x ^ 4 * y ^ 4 * z ^ 2 の約数の個数は75個
result += n4 * (n4 - 1) // 2 * (n2 - 2)
# x ^ 14 * y ^ 4 の約数の個数は75個
result += n14 * (n4 - 1)
# x ^ 24 * y ^ 2 の約数の個数は75個
result += n24 * (n2 - 1)
# x ^ 74 の約数の個数は75個
result += n74
print(result)

Submission status: Accepted

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

ans = sum(x >= 74 for x in l)

a = sum(x >= 2 for x in l)
b = sum(x >= 24 for x in l)
ans += b*(a-1)

a = sum(x >= 4 for x in l)
b = sum(x >= 14 for x in l)
ans += b*(a-1)

a = sum(x >= 2 for x in l)
b = sum(x >= 4 for x in l)
ans += b*(b-1)*(a-2)//2

print(ans)