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:
#!/usr/bin/env python3
from collections import Counter
from functools import reduce
from itertools import permutations
import sys

try:
    from typing import Set, Tuple
except ImportError:
    pass


def factor(n: int):
    k = 2
    while n % k == 0:
        n //= k
        yield k
    k = 3
    while n != 1:
        while n % k == 0:
            n //= k
            yield k
        k += 2


def solve(N: int):
    m = reduce(
        lambda a, b: a + b,
        (
            Counter(factor(i))
            for i in range(1, N + 1)
        )
    )
    # 75 = 3 * 5 * 5 = 3 * 25 = 15 * 5
    qss = [
        [74],
        [2, 4, 4],
        [2, 24],
        [4, 14],
    ]
    nums = set()  # type: Set[Tuple[Tuple[int, int], ...]]
    for qs in qss:
        for ps in permutations(m.keys(), len(qs)):
            if any(m[p] < q for p, q in zip(ps, qs)):
                continue
            num = sorted(zip(ps, qs))
            nums.add(tuple(num))
    print(len(nums))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import factorial
from itertools import permutations

N = int(input())
n_p = factorial(N)

p_list=[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]

ans = []
for p1,p2,p3 in permutations(p_list,3):
    n1 = (p1 ** 4) * (p2 ** 4) * (p3 ** 2)
    n2 = (p1 ** 14) * (p2 ** 4)
    n3 = (p1 ** 24) * (p2 ** 2)
    n4 = p1 ** 74
    
    for v in [n1,n2,n3,n4]:
        if n_p % v == 0:
            ans.append(v)
            
print(len(set(ans)))

Submission status: Accepted

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

# 素因数分解、辞書で返すやつ
# mathをimportする
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
        if num > n:
            break
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor

if n == 1:
    print(0)
    exit()

dic = {}
for a in range(1,n+1):
    pr = prime(a)
    for num, count in pr.items():
        if not num in dic.keys():
            dic[num] = count
        else:
            dic[num] += count
           
over = [0]*5
            
for num,count in dic.items():
    if count + 1 >= 75:
        over[0] += 1
    elif count + 1 >= 25:
        over[1] += 1
    elif count + 1 >= 15:
        over[2] += 1
    elif count + 1 >= 5:
        over[3] += 1
    elif count + 1 >= 3:
        over[4] += 1
        
for i in range(1,5):
    over[i] = over[i] + over[i-1]

ans = over[0]
ans += over[1] * (over[4]-1)
ans += over[2] * (over[3]-1)
ans += (over[4] - over[3]) * (over[3]*(over[3]-1)//2)
ans += over[3] * ((over[3]-1)*(over[3]-2)//2)

print(ans)

Submission status: Accepted

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def factorization(N):
    d = {}
    for n in range(2, N + 1):
        tmp = n
        for i in range(2, int(n ** 0.5) + 1):
            if tmp % i == 0:
                cnt = 0
                while tmp % i == 0:
                    cnt += 1
                    tmp //= i
                if i not in d:
                    d[i] = cnt
                else:
                    d[i] += cnt

        if tmp != 1:
            if tmp not in d:
                d[tmp] = 1
            else:
                d[tmp] += 1

    return d


def main():
    N = int(input())
    d = factorization(N)
    d = [v for k, v in d.items() if v > 1]
    cnt = {2: 0, 4: 0, 14: 0, 24: 0, 74: 0}
    cnt[2] = len(d)
    for i in range(len(d)):
        val = d[i]
        if val >= 74:
            cnt[74] += 1
        if val >= 24:
            cnt[24] += 1
        if val >= 14:
            cnt[14] += 1
        if val >= 4:
            cnt[4] += 1

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def factorization(N):
    d = {}
    for n in range(2, N + 1):
        tmp = n
        for i in range(2, int(n ** 0.5) + 1):
            if tmp % i == 0:
                cnt = 0
                while tmp % i == 0:
                    cnt += 1
                    tmp //= i
                if i not in d:
                    d[i] = cnt
                else:
                    d[i] += cnt

        if tmp != 1:
            if tmp not in d:
                d[tmp] = 1
            else:
                d[tmp] += 1

    return d


def main():
    N = int(input())
    d = factorization(N)
    d = [v for k, v in d.items() if v > 1]
    n = len(d)
    ans = 0
    for i in range(n):
        val = d[i]
        if val >= 74:
            ans += 1

        if val >= 24:
            ans += n - 1

        if val >= 14:
            cnt = 0
            for j in range(n):
                if i == j:
                    continue
                if d[j] >= 4:
                    cnt += 1
            ans += cnt

    cnt_4 = 0
    cnt_2 = 0
    for i in range(n):
        if d[i] >= 4:
            cnt_4 += 1
        else:
            cnt_2 += 1

    ans += (cnt_4 - 1) * cnt_4 // 2 * cnt_2
    ans += (cnt_4 - 2) * (cnt_4 - 1) * cnt_4 // 2

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


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


def main():
    N = int(input())
    A = [0 for _ in range(N + 1)]
    for i in range(1, N + 1):
        F = factorization(i)
        for f in F:
            A[f[0]] += f[1]
    cnt = [0 for _ in range(5)]
    for a in A:
        if a >= 74:
            cnt[0] += 1
        elif a >= 24:
            cnt[1] += 1
        elif a >= 14:
            cnt[2] += 1
        elif a >= 4:
            cnt[3] += 1
        elif a >= 2:
            cnt[4] += 1
    answer = cnt[0]
    answer += sum(cnt[:2]) * sum(cnt[2:])
    answer += sum(cnt[:2]) * (sum(cnt[:2]) - 1)
    answer += sum(cnt[:3]) * (sum(cnt[3:-1]))
    answer += sum(cnt[:3]) * (sum(cnt[:3]) - 1)
    answer += sum(cnt[:4]) * (sum(cnt[:4]) - 1) * cnt[-1] // 2
    answer += sum(cnt[:4]) * (sum(cnt[:4]) - 1) * (sum(cnt[:4]) - 2) // 2
    print(answer)


if __name__ == "__main__":
    main()

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 fac(n):
    ans=1
    for i in range(n,0,-1):
        ans*=i
    return ans

n=int(input())
c = Counter(prime_factorize(fac(n)))
v=c.values()
cnt={74:0,24:0,14:0,4:0,2:0}
for i in v:
    if i>=74:
        cnt[74]+=1
    if i>=24:
        cnt[24]+=1
    if i>=14:
        cnt[14]+=1
    if i>=4:
        cnt[4]+=1
    if i>=2:
        cnt[2]+=1
ans=cnt[74]+cnt[24]*(cnt[2]-1)+cnt[14]*(cnt[4]-1)+cnt[4]*(cnt[4]-1)*(cnt[2]-2)//2
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
import  numpy as np
fact = np.zeros(100)
def prime_factorize(n):
    while n % 2 == 0:
        fact[1]+=1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            fact[f-1] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        fact[n-1] += 1

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

def num(a):
  return sum(fact>=a-1)

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

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template

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())
if N == 1:
    print(0)
    exit()
dp = [[0]*101 for _ in range(N+1)]
for i in range(2,N+1):
    li = factorization(i)
    n = len(li)
    li0 = [0]*n
    li1 = {}
    for k in range(n):
        li0[k] = li[k][0]
        li1[li[k][0]] = li[k][1]
    for j in range(2,101):
        if j in li0:
            dp[i][j] = dp[i-1][j] + li1[j]
            continue
        dp[i][j] = dp[i-1][j]

li = dp[N]
li.sort()
from bisect import bisect_right
indexa = bisect_right(li,0)
lia = li[indexa:]

na = len(lia)
c2 = 0
c4 = 0
c14 = 0
c24 = 0
c74 = 0
for i in range(na):
    if lia[i] >= 2:
        c2+=1
    if lia[i] >= 4:
        c4+=1
    if lia[i] >= 14:
        c14 +=1
    if lia[i] >= 24:
        c24+=1
    if lia[i] >= 74:
        c74+=1
d4_2 = c2-c4
d14_4 = c4 - c14
d24_2 = c2 - c24

def comb2(i):
    return i*(i-1)//2
def comb3(i):
    return i*(i-1)*(i-2)//6

ans = d4_2*comb2(c4) + 3*comb3(c4) + d14_4*c14 + 2*comb2(c14) + d24_2*c24 + 2*comb2(c24) +c74
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
numbers = {2: 0, 3: 0, 5: 0,7: 0, 11: 0, 13: 0, 17: 0, 19: 0, 23: 0, 29: 0, 31: 0, 37: 0, 41: 0, 43: 0, 47: 0, 53: 0, 59: 0, 61: 0, 67: 0, 71: 0, 73: 0, 79: 0, 83: 0, 89: 0, 97: 0}
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)
for n in range(2,N+1):
    a=n
    while(a!=1):
        for j in prime:
            if(a%j==0):
                numbers[j]+=1
                a/=j
n75 = 0
n25 = 0
n15 = 0
n5=0
n3 = 0 
for i in numbers.values():
    if i>=74:
        n75+=1
    if i>=24:
        n25+=1
    if i>=14:
        n15+=1
    if i>= 4:
        n5+=1
    if i>=2:
        n3+=1
ans = n75+n25*(n3-1)+n15*(n5-1)+n5*(n5-1)//2*(n3-2)
print(str(ans)+"\n")

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())

def prime_factorize(n):
    i = 2
    temp = n
    result = []
    while(i * i <= n):
        count = 0
        while temp % i == 0:
            count += 1
            temp //= i
        if count > 0:
            result.append([i, count])
        i += 1
    if temp != 1:
        result.append([temp, 1])
    return result

c = Counter()
for i in range(1, n + 1):
    pf = prime_factorize(i)
    for p in pf:
        c[p[0]] += p[1]

count2 = 0
count4 = 0
count15 = 0
count25 = 0
count75 = 0
for i, v in c.items():
    if v >= 74:
        count75 += 1
    if v >= 24:
        count25 += 1
    if v >= 14:
        count15 += 1
    if v >= 4:
        count4 += 1
    if v >= 2:
        count2 += 1


b = count4 * (count4 - 1) * (count2 - 2) // 2
c = count15 * (count4 - 1)
d = count25 * (count2 - 1)
e = count75


print(b + c + d + e)

Submission status: Accepted

Solution code:
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]]

def calc(p, N):
    ans = 0
    while N != 0:
        N //= p
        ans += N
    return ans

N = int(input())
P = primes(N)
count = []
for i in range(len(P)):
    count.append(calc(P[i], N))
ans = 0
for i in range(len(P)):
    if count[i] >= 74:
        ans += 1

for i in range(len(P)-1):
    for j in range(i+1, len(P)):
        if count[i] >= 2 and count[j] >= 24:
            ans += 1
        if count[i] >= 24 and count[j] >= 2:
            ans += 1
        if count[i] >= 4 and count[j] >= 14:
            ans += 1
        if count[i] >= 14 and count[j] >= 4:
            ans += 1

for i in range(len(P)-2):
    for j in range(i+1, len(P)-1):
        for k in range(j+1, len(P)):
            if count[i] >= 2 and count[j] >= 4 and count[k] >= 4:
                ans += 1
            if count[i] >= 4 and count[j] >= 2 and count[k] >= 4:
                ans += 1
            if count[i] >= 4 and count[j] >= 4 and count[k] >= 2:
                ans += 1

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
soinsu=[0]*N
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 n in range(2,N+1):
  for a in factorization(n):
    soinsu[a[0]-1]+=a[1]
over2=0
over4=0
over14=0
over24=0
over74=0
for i in range(N):
  if soinsu[i]>=74:
    over74+=1
  if soinsu[i]>=24:
    over24+=1
  if soinsu[i]>=14:
    over14+=1
  if soinsu[i]>=4:
    over4+=1
  if soinsu[i]>=2:
    over2+=1
print(over74 + over24*(over2-1) + over14*(over4-1) + over4*(over4-1)*(over4-2)//2 + (over2-over4)*over4*(over4-1)//2)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()

d = [1 for _ in range(100)]

for i in range(1,N+1):
    j = 2
    while i > 1:
        if i % j == 0:
            d[j] += 1
            i //= j
        else:
            j += 1
n3 = 0
n5 = 0
n15 = 0
n25 = 0
n75 = 0
for x in d:
    if x >= 3: n3 += 1
    if x >= 5: n5 += 1
    if x >=15: n15 +=1
    if x >=25: n25 +=1
    if x >=75: n75 +=1
ans = (n3-n5) * ((n5) * (n5-1) // 2) + (n5) * (n5-1) * (n5-2) // 2
ans += (n5 - n15) * n15 + (n15) * (n15-1)
ans += (n3 - n25) * n25 + (n25) * (n25-1)
ans += n75
print (ans)

Submission status: Accepted

Solution code:
N = int(input())

def solve(N):
    seventyfour = [78,101]
    twentyfour = [28,54,100,101]
    fourteen = [16,30,60,91,101]
    four = [6,9,20,28,44,52,68,76,92,116]
    two = [4,6,10,14,22,26,34,38,46,58,62,74,82,86,94,106]
    lists = [two,four,fourteen,twentyfour,seventyfour]
    nums = []
    for lis in lists:
        for i,n in enumerate(lis):
            if N<n:
                nums.append(i)
                break
    ans = nums[1]*(nums[1]-1)//2*(nums[0]-2)+nums[2]*(nums[1]-1)+nums[3]*(nums[0]-1)+nums[4]
    return ans
print(solve(N))

Submission status: Accepted

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


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


d = defaultdict(lambda: 0)
for i in range(2, n+1):
    a = factorization(i)
    for aa, k in a:
        d[aa] += k
t = [v for v in d.values()]


def num(t, a):
    return sum([1 if tt >= a-1 else 0 for tt in t])


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

Submission status: Accepted

Solution code:
def main():
    from collections import Counter

    N = int(input())

    p = [0] * (N + 1)
    for x in range(2, N + 1):
        d = 2
        cnt = 0
        while x % d == 0:
            x //= d
            cnt += 1
        p[d] += cnt

        d = 3
        while x > 1:
            cnt = 0
            while x % d == 0:
                x //= d
                cnt += 1
            p[d] += cnt
            d += 2

    ctr = Counter(p)

    def count(n):
        ret = 0
        for pw, cnt in ctr.items():
            if pw >= n - 1:
                ret += cnt
        return ret

    def choose(n, r):
        x, y = 1, 1
        for i in range(r):
            x *= n - i
            y *= i + 1
        return x // y

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

    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
exp = [0] * (N+1)
for i in range(2, N+1):
    cur = i
    for p in range(2, i+1):
        while cur % p == 0:
            exp[p] += 1
            cur //= p

def num(x):
    '''冪乗がx-1以上の数を返す'''
    return len(list(filter(lambda y: y >= x-1, exp)))

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
power = [0] * (N+1)
for x in range(2, N+1):
    for p in range(2, x+1):
        while x % p == 0:
            power[p] += 1
            x //= p

def num(x):
    '''約数がx-1以上の数を返す'''
    return len(list(filter(lambda y: y >= x-1, power)))

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

Submission status: Accepted

Solution code:
from collections import defaultdict

def dfs(i, comb):
    key = (i, comb)
    if key in memo:
        return memo[key]
    if comb == 75:
        return 1
    if i == m:
        return 0
    k, v = p[i]
    res = 0
    for j in range(v + 1):
        if comb * (j + 1) <= 75:
            res += dfs(i + 1, comb * (j + 1))
    memo[key] = res
    return res

n = int(input())
index = defaultdict(int)

for x in range(2, n + 1):
    y = 2
    while y ** 2 <= x:
        while x % y == 0:
            x //= y
            index[y] += 1
        y += 1
    if x > 1:
        index[x] += 1

*p, = index.items()
m = len(p)
memo = {}
print(dfs(0, 1))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
import sys
input = sys.stdin.readline


def getPrimes(n):
    isPrime = [True] * n
    ret = []
    for p in range(2, n):
        if not isPrime[p]:
            continue
        ret.append(p)
        for i in range(p, n, p):
            isPrime[i] = False
    return ret


def main():
    N = int(input())
    P = getPrimes(N)
    C = Counter()

    for i in range(1, N + 1):
        cnt = Counter()
        for p in P:
            while i % p == 0:
                i //= p
                cnt[p] += 1
        C += cnt

    d = {3: 0, 5: 0, 15: 0, 25: 0, 75: 0}
    for k in d.keys():
        for v in C.values():
            if v >= k - 1:
                d[k] += 1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import factorial
from itertools import permutations

n=int(input())
np=factorial(n)
p_list=[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]

ans=[]
for s,t,u in permutations(p_list,3):
  num1=(s**4)*(t**4)*(u**2)
  num2=(s**14)*(t**4)
  num3=(s**24)*(t**2)
  num4=s**74
  for z in [num1,num2,num3,num4]:
    if np%z==0:
      ans.append(z)

print(len(set(ans)))

Submission status: Accepted

Solution code:
from math import factorial
from itertools import permutations

def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p, p_list

n=int(input())
np=factorial(n)

lim=10**2+1
is_p, p_list=eratosthenes(lim)

ans=[]
for s,t,u in permutations(p_list,3):
  num1=(s**4)*(t**4)*(u**2)
  num2=(s**14)*(t**4)
  num3=(s**24)*(t**2)
  num4=s**74
  for z in [num1,num2,num3,num4]:
    if np%z==0:
      ans.append(z)

print(len(set(ans)))

Submission status: Accepted

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

from collections import Counter
c=Counter(a)
c=c.most_common()
c3=0
c5=0
c15=0
c25=0
c75=0
for k,v in c:
  if 2<=v<4:c3+=1
  elif 4<=v<14:c5+=1
  elif 14<=v<24:c15+=1
  elif 24<=v<74:c25+=1
  elif 74<=v:c75+=1
c3=c3+c5+c15+c25+c75
c5=c5+c15+c25+c75
c15=c15+c25+c75
c25=c25+c75
ans=0
ans+=(c5*(c5-1)//2)*(c3-2)
ans+=c15*(c5-1)
ans+=c25*(c3-1)
ans+=c75
print(ans)

Submission status: Accepted

Solution code:
from math import factorial
from itertools import permutations

n=int(input())

np=factorial(n)

def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p, p_list

lim=10**2+1
is_p, p_list=eratosthenes(lim)

cnt=0
ans=[]
l=len(p_list)
for i in range(l):
  for j in range(i+1,l):
    for k in range(j+1,l):
      for s,t,u in permutations([p_list[i],p_list[j],p_list[k]],3):
        num1=(s**4)*(t**4)*(u**2)
        num2=(s**14)*(t**4)
        num3=(s**24)*(t**2)
        num4=s**74
        for z in [num1,num2,num3,num4]:
          if np%z==0:
            ans.append(z)

print(len(set(ans)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    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


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
# https://atcoder.jp/contests/abc114/tasks/abc114_d

N = read_a_int()

# N!を素因数分解形式で表示する
# その結果ni>=74となる 因数の個数
# +
# ni >= 24 かつ nj >=2となる因数の組の個数
# +
# ni >= 14 かつ nj >=4となる因数の組の個数
# +
# ni >= 4 かつ nj >=4 かつ nk >=2 となる因数の組の個数
# が答えのはず
# 素数は少ないので全探索できそう

N_fact = defaultdict(lambda: 0)
for i in ra(1, N + 1):
    tmp = factorization(i)
    for k, v in tmp:
        N_fact[k] += v

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

# print(ans)
for i, j in product(range(len(values)), repeat=2):
    if i == j:
        continue
    if values[i] >= 24 and values[j] >= 2:
        ans += 1
    if values[i] >= 14 and values[j] >= 4:
        ans += 1


# ここまで多分ok

# print(ans)
for i, j in combinations(range(len(values)), r=2):  # i,jはダブらないように選ぶ
    for k in range(len(values)):
        if i == k or j == k:
            continue
        if values[i] >= 4 and values[j] >= 4 and values[k] >= 2:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
if n == 1:
    print(0)
    exit()

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


pms = primes(n)
num = [0]*len(pms)
ans = 0
for j in range(2,n+1):
    for i in range(len(pms)):
        while j % pms[i] == 0:
            j //= pms[i]
            num[i] += 1
c74 = 0
c24 = 0
c14 = 0
c4 = 0
c2 = 0
for i in range(len(num)):
    if num[i] >= 74:
        c74 += 1
        c24 += 1
        c14 += 1
        c4 += 1
        c2 += 1
    elif num[i] >= 24:
        c24 += 1
        c14 += 1
        c4 += 1
        c2 += 1
    elif num[i] >= 14:
        c14 += 1
        c4 += 1
        c2 += 1
    elif num[i] >=4:
        c4 += 1
        c2 += 1
    elif num[i] >= 2:
        c2 += 1
ans += c74
ans += c24 * (c2-1)
ans += c14 * (c4-1)
ans += c4*(c4-1)//2 * (c2-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,10):
    for j in range(i*i,100,i):
        P[j] = 0
Q = []
for i in range(100):
    if P[i]==1:
        Q.append(i)
C = {i:0 for i in Q}
N = int(input())
for i in range(2,N+1):
    x = i
    for p in C:
        while x%p==0:
            x = x//p
            C[p] += 1
#2 4 4
c2 = 0
c4 = 0
for p in C:
    if 2<=C[p]<4:
        c2 += 1
    elif C[p]>=4:
        c4 += 1
cnt = c2*((c4*(c4-1))//2)+c4*(((c4-1)*(c4-2))//2)
#2 24
c2 = 0
c24 = 0
for p in C:
    if 2<=C[p]<24:
        c2 += 1
    elif C[p]>=24:
        c24 += 1
cnt += c2*c24+c24*(c24-1)
#4 14
c4 = 0
c14 = 0
for p in C:
    if 4<=C[p]<14:
        c4 += 1
    elif C[p]>=14:
        c14 += 1
cnt += c4*c14+c14*(c14-1)
#75
c74 = 0
for p in C:
    if C[p]>=74:
        c74 += 1
cnt += c74
print(cnt)

Submission status: Accepted

Solution code:
def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes
N=int(input())
primes=get_primes(N)
numbers=[]
for i in primes:
  temp=0
  j=1
  while i**j<=N:
    temp+=N//(i**j)
    j+=1
  numbers.append(temp)
counter3=0
counter5=0
counter15=0
counter25=0
counter75=0
for i in numbers:
  if i>1:
    counter3+=1
  if i>3:
    counter5+=1
  if i>13:
    counter15+=1
  if i>23:
    counter25+=1
  if i>73:
    counter75+=1
print(counter75+(counter5-1)*counter15+(counter3-1)*counter25+(counter3-2)*(counter5-1)*counter5//2)

Submission status: Accepted

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

def getPrimes():
    isPrime = [True] * 100
    primes = []
    for p in range(2, 100):
        if not isPrime[p]:
            continue
        primes.append(p)
        for i in range(p, 100, p):
            isPrime[i] = False
    return primes

P = getPrimes()
A = Counter()

for n in range(1, N + 1):
    cnt = Counter()
    for p in P:
        while n % p == 0:
            n //= p
            cnt[p] += 1
    A += cnt

D = {3: 0, 5: 0, 15: 0, 25: 0, 75: 0}
for k in D.keys():
    for c in A.values():
        if (c + 1) >= k:
            D[k] += 1

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

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())

dic = defaultdict(int)


def factoring(k): #kを因数分解し、素因数とその個数を辞書に入れて返す。
    import math
    n = int(math.sqrt(k))+2
    for i in range(2, n):
        count = 0
        while k%i == 0:
            count += 1
            k = k//i
        if count != 0:
            dic[i] += count
    if k != 1: #sqrt(k)までチェックしてもkが1になっていない --> kが素因数
        dic[k] += 1
    return

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

ans = 0
for i in dic:
    if dic[i] >= 74:
        ans += 1
    if dic[i] >= 2:
        count = 0
        for j in dic:
            if i == j:
                continue
            if dic[j] >= 4:
                count += 1
        ans += count * (count - 1) // 2
    if dic[i] >= 2:
        for j in dic:
            if i == j:
                continue
            if dic[j] >= 24:
                ans += 1
    if dic[i] >= 4:
        for j in dic:
            if i == j:
                continue
            if dic[j] >= 14:
                ans += 1

print (ans)
# print (dic)

Submission status: Accepted

Solution code:
# nを素因数分解したリストを返す
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

n = int(input())

from collections import defaultdict
dic = defaultdict(int)

for i in range(1, n+1):
    for prime in prime_decomposition(i):
        dic[prime] += 1

values = dic.values()

up2 = 0
up4 = 0
up14 = 0
up24 = 0
up74 = 0
for d in values:
    if d >= 74:
        up74 += 1
    if d >= 24:
        up24 += 1
    if d >= 14:
        up14 += 1
    if d >= 4:
        up4 += 1
    if d >= 2:
        up2 += 1

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

ans = 0
#75
ans += up74
#25*3
ans += up24 * (up2 - 1)
#15*5
ans += up14 * (up4 - 1)
#5*5*3
ans += up4 * (up4 - 1) * (up2-2) // 2


print(ans)