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:
from collections import defaultdict
import math
def main():
    def factorization(num):
        nonlocal d
        if num in primes:
            d[num] += 1
            return
        for prime in primes:
            if num % prime == 0:
                count = 0
                while num % prime == 0:
                    count += 1
                    num //= prime
                d[prime] += count

    def generate_primes(num):
        if num == 1: return []
        primes = list(range(2, num + 1))
        i, p = 0, 1
        while p <= math.sqrt(num):
            if primes[i] != 0:
                p = primes[i]
                primes = [prime if (prime % p != 0 or prime == p) else 0 for prime in primes]
            i += 1
        return set(p for p in primes if p != 0)

    n = int(input())
    d = defaultdict(lambda :1)
    primes = generate_primes(100)
    for i in range(1, n + 1):
        factorization(i)
    c = [0] * 6
    for v in d.values():
        if v >= 3: c[0] += 1
        if v >= 75: c[5] -= 1
        elif v >= 25: c[4] -= 1
        elif v >= 15: c[3] -= 1
        elif v >= 5: c[2] -= 1
        elif v >= 3: c[1] -= 1
    s = 0
    for i in range(6):
        s += c[i]
        c[i] = s
    print(c[1] * (c[1] - 1) * (c[0] - 2) // 2 + c[3] * (c[0] - 1) + c[2] * (c[1] - 1) + c[4])
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
def factor(n, m=None):
    # mを与えると、高々その素因数まで見て、残りは分解せずにそのまま出力する
    arr = {}
    temp = n
    M = int(-(-n**0.5//1))+1
    if m is not None:
        M = min(m+1, M)
    for i in range(2, M):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if not arr:
        arr[n] = 1

    return arr
from collections import defaultdict
d = defaultdict(int)
for i in range(2, n+1):
    dd = factor(i)
    for k,v in dd.items():
        d[k] += dd[k]
n74 = sum(v>=74 for v in d.values())
n2 = sum(v>=2 for v in d.values())
n24 = sum(v>=24 for v in d.values())
n14 = sum(v>=14 for v in d.values())
n4 = sum(v>=4 for v in d.values())
ans = n74 + (n2-1)*n24 + (n4-1)*n14 + (n4*(n4-1)//2 * (n2-2) if n4>=1 else 0)
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:
import math
n = int(input())

div = [0]*101

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

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

for i in range(n):
    if div[i]>=2:
        n2+=1
    if div[i]>=4:
        n4+=1
    if div[i]>=14:
        n14+=1
    if div[i]>=24:
        n24+=1
    if div[i]>=74:
        n74+=1

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

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    n = int(ipt())
    d = defaultdict(int)
    #nまでの素数の配列を返す関数
    def primes(n):
        if n == 1:
            return []
        else:
            tbl = [True]*(n+1)
            pri = [2]
            for i in range(2,n+1,2):
                tbl[i] = False
            k = 3
            while k <= n:
                if tbl[k]:
                    pri.append(k)
                    for i in range(k,n+1,k):
                        tbl[i] = False
                k += 2
            return pri
    p = primes(n)
    for i in range(2,n+1):
        ii = i
        for j in p:
            while True:
                if ii%j == 0:
                    d[j] += 1
                    ii //= j
                else:
                    break
            if ii == 1:
                break
    d2 = 0
    d4 = 0
    d14 = 0
    d24 = 0
    d74 = 0
    for i in d.values():
        if i >= 2:
            d2 += 1
            if i >= 4:
                d4 += 1
                if i >= 14:
                    d14 += 1
                    if i >= 24:
                        d24 += 1
                        if i >= 74:
                            d74 += 1

    print(d4*(d4-1)*(d2-2)//2+d14*(d4-1)+d24*(d2-1)+d74)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
P = 10**9+7
  
memo = [0]*(N+1)

for i in range(1,N+1):
  j = i
  while j % 2 == 0:
    memo[2] += 1
    j //= 2
  k = 3
  while k*k <= j:
    if j % k == 0:
      memo[k] += 1
      j //= k
    else:
      k += 2
  if j != 1:
    memo[j] += 1
  
rlt = 0
dic = {2:0, 4:0, 14:0, 24:0, 74:0}
for i in range(1, N+1):
  if memo[i] >= 74:
    dic[74] += 1
  if memo[i] >= 24:
    dic[24] += 1
  if memo[i] >= 14:
    dic[14] += 1
  if memo[i] >= 4:
    dic[4] += 1
  if memo[i] >=2:
    dic[2] += 1
    

rlt += dic[74]
rlt += dic[24]*(dic[2]-1)
rlt += dic[14]*(dic[4]-1)
rlt += dic[4]*(dic[4]-1)*(dic[2]-2)//2

print(rlt)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

    return arr


N = int(input())

prime = dict()
for i in range(2, N+1):
    prime_i = factorization(i)
    for p, num in prime_i:
        if p in prime:
            prime[p] += num
        else:
            prime[p] = num

divisor_75 = 0
divisor_25 = 0
divisor_15 = 0
divisor_5 = 0
divisor_3 = 0
for v in prime.values():
    if v >= 74:
        divisor_75 += 1
    if v >= 24:
        divisor_25 += 1
    if v >= 14:
        divisor_15 += 1
    if v >= 4:
        divisor_5 += 1
    if v >= 2:
        divisor_3 += 1

ans = 0
ans += divisor_75
ans = max(ans, ans + divisor_25 * (divisor_3 - 1))
ans = max(ans, ans + divisor_15 * (divisor_5 - 1))
ans = max(ans, ans + ((divisor_5 * (divisor_5 - 1)) // 2) * (divisor_3 - 2))

print(ans)

Submission status: Accepted

Solution code:
class Prime:
    # https://qiita.com/daikw/items/f48d6ac374255763463d
    seed_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
    ]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

        :param n:
        :return: boolean
        """
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed + 1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes


import collections
N = int(input())
c = collections.defaultdict(int)
for i in range(1, N + 1):
    factors = Prime().find_factors(i)
    for k, v in factors.items():
        c[k] += v
d = c.values()
#3*5*5=3*25=5*15=75
#a^b*c^dの約数は(b+1)*(d+1)個
n75 = sum(i >= 74 for i in d)
n25 = sum(i >= 24 for i in d)
n15 = sum(i >= 14 for i in d)
n5 = sum(i >= 4 for i in d)
n3 = sum(i >= 2 for i in d)

ans = n5 * (n5 - 1) * (n3 - 2) // 2
ans += n25 * (n3 - 1)
ans += n15 * (n5 - 1)
ans += n75
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def sieve(N):
    p = 0
    prime = []
    is_prime = [1 for _ in range(N + 1)]
    is_prime[0], is_prime[1] = 0, 0
    for i in range(2, N + 1):
        if is_prime[i]:
            p += 1
            temp = i
            prime.append(i)
            while(temp <= N):
                is_prime[temp] = 0
                temp += i
            is_prime[i] = 1
    return p, prime

def fact_prime(n, p):
    ret = 0
    temp = p
    while(n >= p):
        ret += n // p
        p *= temp
    return ret

_, prime_list = sieve(N)
ans = 0

for a in prime_list:
    for b in prime_list:
        for c in prime_list:
            if a != b and b < c and a != c:
                if fact_prime(N, a) >= 2 and fact_prime(N, b) >= 4 and fact_prime(N, c) >= 4:
                    ans += 1
                    
for a in prime_list:
    for b in prime_list:
        if b != a:
            if fact_prime(N, a) >= 24 and fact_prime(N, b) >= 2:
                ans += 1
            if fact_prime(N, a) >= 4 and fact_prime(N, b) >= 14:
                ans += 1
                
for a in prime_list:
    if fact_prime(N, a) >= 74:
        ans += 1    

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def cal_divisors(N):
    divisors = []
    i = 1
    while i*i <= N:
        if N % i == 0:
            divisors.append(i)
            if i != N // i:
                divisors.append(N//i)
        i += 1
    divisors.sort()
    return divisors

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

def main():
    N = int(input())
    divisors = []
    for i in range(1,N+1):
        divisors.extend(prime_factorize(i))
    l = Counter(divisors)
    # print(l)
    # 約数を75個持つ X = a^p * b^q とした時、(p,q) = (0,74), (2,24), (4,14) しかない
    ans = 0
    nums = l.values()
    # 74より大きい素因数の数だけ(1)のパターン
    ans += len([*filter(lambda x: x >= 74, nums)])

    # 14,4のパターン
    ans += len([*filter(lambda x: x >= 14, nums)]) * (len([*filter(lambda x: x >= 4, nums)])-1)

    # 24,2のパターン
    ans += len([*filter(lambda x: x >= 24, nums)]) * (len([*filter(lambda x: x >= 2, nums)])-1)

    # 4,4,2のパターン
    ans += len([*filter(lambda x: x >= 4, nums)]) * (len([*filter(lambda x: x >= 4, nums)])-1) * (len([*filter(lambda x: x >= 2, nums)])-2) // 2

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import math

N = int(input())
D = defaultdict(int)

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 prime_cnt(p, n):
  cnt = 0
  temp = p
  while temp <= n:
    cnt += n//temp
    temp *= p
  return cnt

def conb(n, r):
  if n <= 0 or n < r:
    return 0
  elif r == 1:
    return n
  else:  
    return n * (n-1) // 2

for p in primes(N):
  D[p] += prime_cnt(p, N)

C = [0]*5
L = [3, 5, 15, 25, 75]

for i in D.values():
  for j in range(5):
    if i >= L[j] - 1:
      C[j] += 1

ans = 0
ans += conb(C[4], 1)
ans += conb(C[3], 1) * conb(C[0]-1, 1)
ans += conb(C[2], 1) * conb(C[1]-1, 1)
ans += conb(C[1], 2) * conb(C[0]-2, 1)

print(ans)

Submission status: Accepted

Solution code:
#素因数分解
def soinsu_bunkai(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


# 初期入力
from collections import Counter
from collections import defaultdict
from itertools import permutations
import sys
input = sys.stdin.readline  #文字列では使わない
N = int(input())

# Nの階乗の素数列挙
c =defaultdict(int)
for i in range(1,N+1):
    x =soinsu_bunkai(i)
    for j,v in x.items():
        c[j] +=v


ans=set()
for p,q,r in permutations(c.keys(),3):
    if c[p] >=74:
        ans.add(p**74)
    if c[p] >=24 and c[q] >=2:
        ans.add((p**24)*(q**2))
    if c[p] >=14 and c[q] >=4:
        ans.add((p**14)*(q**4))
    if c[p] >=4 and c[q] >=4 and c[r] >=2:
        ans.add((p**4)*(q**4)*(r**2))
    
print(len(ans))

Submission status: Accepted

Solution code:
n = int(input())
def count_factors(n, factors):
    factors.setdefault(2, 0)
    while n%2 == 0:
        factors[2] += 1
        n //=2

    for f in range(3, int(n**0.5)+ 1, 2):
        factors.setdefault(f, 0)
        while n%f == 0:
            factors[f] += 1
            n //= f
    if n != 1:
        factors.setdefault(n, 0)
        factors[n] += 1


cf = {1: 1}
for i in range(1, n+1):
    count_factors(i, cf)

# 約数が75個になるように選ぶ
ans = 0
c25 = 0
c15 = 0
c5 = 0
c3 = 0
c2 = 0
for v in cf.values():
    if v >= 74:
        ans += 1
    if v >= 24:
        c25 += 1
    if v >= 14:
        c15 += 1
    if v >= 4:
        c5 += 1
    if v >= 2:
        c3 += 1
    if v >= 1:
        c2 += 1

ans += c25 *(c3 - 1)
ans += c15 *(c5 - 1)
ans += c5 * (c5-1) * (c3-2)//2
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

from collections import defaultdict
import itertools
def soinsu(n):
    arr = []
    now = n
    for i in range(2, int(n**0.5)+1):
        if now%i==0:
            cnt=0
            while now%i==0:
                cnt+=1
                now //= i
            arr.append([i, cnt])
    if now!=1:
        arr.append([now, 1])
#     if arr==[]:
#         arr.append([n, 1])
    return arr

d = defaultdict(int)
for i in range(1,N+1):
    bunkai =soinsu(i)
    for b in bunkai:
        d[b[0]]+=b[1]

prime_list=[k for k in d.keys() if d[k]>=2]

N2 = sum(d[k]>=2 for k in d.keys())
N4 = sum(d[k]>=4 for k in d.keys())

N14 = sum(d[k]>=14 for k in d.keys())
N24 = sum(d[k]>=24 for k in d.keys())
N74 = sum(d[k]>=74 for k in d.keys())

pattern2_4_4 = N4*(N4-1)*(N2-2)//2
pattern2_24 = N24*(N2-1)
pattern4_14 = N14*(N4-1)
pattern74 = N74

print(pattern2_4_4 + pattern2_24 + pattern4_14+pattern74)

Submission status: Accepted

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

#N！を素因数分解した時の指数を列挙
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
# print(e)
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:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def is_prime(n):
    if n == 1:
        return False
    for k in range(2, int(pow(n, 0.5)) + 1):
        if n % k == 0:
            return False
    return True


def resolve():
    n = int(input())
    primes = []
    for i in range(1, n + 1):
        if is_prime(i):
            primes.append(i)

    fact = []
    for prime in primes:
        ex = 0
        p = prime
        while n // p:
            ex += n // p
            p *= prime
        fact.append(ex)

    cnt_74 = cnt_24 = cnt_14 = cnt_4 = cnt_2 = 0
    for i in fact:
        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

    res1 = max(0, cnt_24 * (cnt_2 - 1))
    res2 = (cnt_4 * (cnt_4 - 1)) // 2 * max(0, cnt_2 - 2)
    res3 = max(0, cnt_14 * (cnt_4 - 1))
    print(cnt_74 + res1 + res2 + res3)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())

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

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

up2 = 0
up4 = 0
up24 = 0
up14 = 0
up74 = 0
for i, p in enumerate(primes):
    if p>=2:
        up2 += 1
    if p>=4:
        up4 += 1
    if p>=24:
        up24 += 1
    if p>=14:
        up14 += 1
    if p>=74:
        up74 += 1

ans = 0
if up4>=2:
    ans += (up2-2)*(up4*(up4-1)//2)
if up24>=1:
    ans += (up2-1)*up24
if up14>=1:
    ans += (up4-1)*up14
if up74>=1:
    ans += up74

print(ans)

Submission status: Accepted

Solution code:
N=int(input())

prime_factorization={}
for i in range(1,N+1):
	d=2
	orig=i
	while d< (int(orig**0.5)+1):
		while i%d==0:
			i=i//d
			if d in prime_factorization:
				prime_factorization[d]+=1
			else:
				prime_factorization[d]=1
		d+=1
	if i>1:
		if i in prime_factorization:
			prime_factorization[i]+=1
		else:
			prime_factorization[i]=1

greater2=0
greater4=0
greater14=0
greater24=0
greater74=0
for i in prime_factorization:
	if prime_factorization[i]>=2:
		greater2+=1
	if prime_factorization[i]>=4:
		greater4+=1
	if prime_factorization[i]>=14:
		greater14+=1
	if prime_factorization[i]>=24:
		greater24+=1
	if prime_factorization[i]>=74:
		greater74+=1
combi3=((greater4*(greater4-1))//2)*(greater2-2)
combi2=(greater14)*(greater4-1) + (greater24)*(greater2-1)
combi1=greater74
print(combi1+combi2+combi3)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def conb(n,r): 
    if n<r: return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def prime_factorize(n):
    if n == 1:
        return [1]
    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 = inp()
d = defaultdict(int)
for i in range(1,n+1):
    for x in prime_factorize(i):
        d[x] += 1

valist = d.values()
c = [2,4,14,24,74]
cnt = [0] * 5
for x in valist:
    if x >= 74: cnt[4] += 1
    elif x >= 24: cnt[3] += 1
    elif x >= 14: cnt[2] += 1
    elif x >= 4: cnt[1] += 1
    elif x >= 2: cnt[0] += 1
# print(cnt)
res = 0
a = sum(cnt[1:]); b = cnt[0]
res += conb(a,3)*3 + conb(a,2)*b
a = sum(cnt[2:]); b = cnt[1]
res += a*(a-1) + a*b
a = sum(cnt[3:]); b = sum(cnt[:3])
res += a*(a-1) + a*b
res += cnt[4]
print(res)

Submission status: Accepted

Solution code:
import itertools
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5) #ルートn以上で割れることはない
    data = [i + 1 for i in range(2, n, 2)] #最初から3スタートの奇数にしておく
    while True:
        p = data[0]
        if limit < p: #ここでイコールが入るとlimitが素数の時にlimit^2が残ってダメ。
            return prime + data
        prime.append(p) #ここで一番最初に取り出した素数を加える。
        data = [e for e in data if e % p != 0] #残りでその素数で割れない数字を取得。

Sosu = get_sieve_of_eratosthenes(100)
#print(Sosu)
N = int(input())
limit = 1
for i in range(N):
  limit *= i+1
ans = 0
A = [0]*len(Sosu)
for i in range(1,N+1):
  now = i*1
  for j in range(len(Sosu)):
    while now%Sosu[j] == 0:
      A[j] += 1
      now //= Sosu[j]
    if now == 1:
      break
#print(A)
ans = 0
for i in A:
  if i >= 74:
    ans +=1
T = list(itertools.permutations(A,2)) #順列
for L in T:
  first,second = L
  if first >= 4 and second >= 14:
    ans += 1
  if first >= 2 and second >= 24:
    ans += 1
T = list(itertools.permutations(A,3)) #順列
#print(T)
temp = 0
for L in T:
  first,second,third = L
  if first >= 2 and second >= 4 and third >= 4:
    temp += 1
temp = temp//2
ans += temp
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations

n=int(input())

def factorization(n):
    p=2
    fcr=[]
    while p*p<=n:
        while n%p==0:
            fcr.append(p)
            n//=p
        p+=1
    if n>1:
        fcr.append(n)
    return fcr


fcr_l=[]
for i in range(1,n+1):
  fcr=factorization(i)
  fcr_l+=fcr


c=Counter(fcr_l)
fcr_st=set(fcr_l)

ans=[]
for p,q,r in permutations(fcr_st,3):
  if c[p]>=74:
    ans.append(p**74)
  if c[p]>=24 and c[q]>=2:
    ans.append((p**24)*(q**2))
  if c[p]>=14 and c[q]>=4:
    ans.append((p**14)*(q**4))
  if c[p]>=4 and c[q]>=4 and c[r]>=2:
    ans.append((p**4)*(q**4)*(r**2))

print(len(set(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(2,100):
    if P[i]==1:
        Q.append(i)
C = {q:0 for q in Q}
N = int(input())
for i in range(2,N+1):
    x = i
    for q in Q:
        while x%q==0:
            x = x//q
            C[q] += 1
D = {2:0,4:0,14:0,24:0,74:0}
for q in Q:
    if C[q]>=2:
        D[2] += 1
    if C[q]>=4:
        D[4] += 1
    if C[q]>=14:
        D[14] += 1
    if C[q]>=24:
        D[24] += 1
    if C[q]>=74:
        D[74] += 1
cnt = D[74]
cnt += (D[2]-D[24])*D[24]+(D[24]*(D[24]-1))
cnt += (D[4]-D[14])*D[14]+(D[14]*(D[14]-1))
cnt += (D[2]-D[4])*(D[4]*(D[4]-1))//2+(D[4]*(D[4]-1)*(D[4]-2))//2
print(cnt)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret

def geteach(n):
    ret = defaultdict(int)
    for i in range(2, n+1):
        while True:
            if n % i == 0:
                ret[i] += 1
                n //= i
            else:
                break

        if n == 1:
            break

    return ret


def getyaku(n):
    ret = defaultdict(int)

    for i in range(2, n+1):
        fac = geteach(i)
        for k, v in fac.items():
            ret[k] += v

    return ret

def solve():

    n = getN()
    yaku = (getyaku(n))
    # print(yaku)
    nanashi = 0
    yon = 0
    ni = 0
    nishi = 0
    ichisi = 0
    for v in yaku.values():
        if v >= 74:
            nanashi += 1
        if v >= 24:
            nishi += 1
        if v >= 14:
            ichisi += 1
        if v >= 4:
            yon += 1
        if v >= 2:
            ni += 1

    if yon < 2 or yon + ni < 3:
        print(0)
        return
    pat1 = nanashi
    pat2 = nishi * (ni - 1)
    pat3 = ichisi * (yon - 1)
    pat4 = yon * (yon-1) * (ni - 2) // 2

    print(max(pat1, 0) + max(pat2, 0) + max(pat3, 0) + max(pat4, 0))

def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
n = int(input())
def factorize(n,factors):
	d = 2
	orig_n = n
	while d*d <= orig_n and n > 1:
		while n%d==0:
			factors[d] = factors.get(d,0)+1
			n //= d 
		d += 1
	if n > 1:
		factors[n] = factors.get(n,0)+1
def geq(val,factors):
	return len([x for x in factors if factors[x] >= val])

factors = {}
for i in range(1,n+1):
	factorize(i,factors)

ans = 0
ans += geq(74,factors)
ans += geq(24,factors)*(geq(2,factors)-1)
ans += geq(14,factors)*(geq(4,factors)-1)
ans += (geq(4,factors)*(geq(4,factors)-1)//2)*(geq(2,factors)-2)

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]

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


def main():
    N = NI()
    PD = {}
    for i in range(2, N+1):
        pd = prime_fact(i)
        for p, k in pd.items():
            PD.setdefault(p, 0)
            PD[p] += k
    X = {74: 0, 24: 0, 14: 0, 4: 0, 2: 0}
    for p, k in PD.items():
        for x in X.keys():
            if k >= x:
                X[x] += 1
    print(X[74] + X[24]*(X[2]-1) + X[14]*(X[4]-1) + X[4]*(X[4]-1)//2 * (X[2]-2))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

primes = set(range(2, N+1))
for i in range(2, int(N**0.5+1)):
    primes.difference_update(range(i*2, N+1, i))
primes = list(primes)
primes.sort()

div = [0]*len(primes)

for i in range(2, N+1):
    num = i
    for j, prime in enumerate(primes):
        cnt = 0
        if num < prime: break
        while num%prime == 0:
            cnt += 1
            num //= prime
        div[j] += cnt
        
c74, c24, c14, c4, c2 = 0, 0, 0, 0, 0
for i in div:
    if i>= 74: c74 += 1
    if i >= 24: c24 += 1
    if i >= 14: c14 += 1
    if i >= 4: c4 += 1
    if i >= 2: c2 += 1
ans = 0
ans += c74
ans += (c24) * (c2 - 1)
ans += c14 * (c4 - 1)
ans += (c4) * (c4 - 1) // 2 * (c2 - 2)
print(ans)