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:
import itertools
n=int(input())
prime=[2]
d={2:0}
for i in range(3, 100):
    if all(i%p!=0 for p in prime):
        prime.append(i)
        d[i]=0
for i in range(1, n+1):
    tmp=i
    for p in prime:
        while tmp%p==0:
            d[p]+=1
            tmp//=p
cnt4=0
cnt2=0
cnt74=0
cnt14=0
cnt24=0
for p in prime:
    if d[p]>=4:
        cnt4+=1
    if d[p]>=2:
        cnt2+=1
    if d[p]>=74:
        cnt74+=1
    if d[p]>=14:
        cnt14+=1
    if d[p]>=24:
        cnt24+=1
print(max(0,(cnt4)*(cnt4-1)*(cnt2-2)//2)+max(0, cnt74)+max(0, cnt14*(cnt4-1))+max(0, cnt24*(cnt2-1)))

Submission status: Accepted

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

for i in range(2, N+1):
	# Nまでの要素について順に因数分解していく
	cnt = i
	for j in range(2, i+1):
		# ひたすらjで因数分解して、jについての指数を求める
		while cnt%j == 0:
			a[j] += 1
			cnt //=j

def num(m):
	ret = 0
	for i in range(2, N+1):
		if a[i] >= m:
			ret += 1
	return ret

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = list(map(int,S()))
    l = len(n)
    dp = [[[0 for k in range(16)] for j in range(2)] for i in range(l+1)]
    dp[0][0][0] = 1
    for i in range(l):
        for j in range(2):
            for k in range(9):
                x = 9 if j else n[i]
                for d in range(x+1):
                    if d == 3:
                        f = 1
                    elif d == 5:
                        f = 2
                    elif d == 7:
                        f = 4
                    else:
                        if k == 0 and d == 0:
                            f = 0
                        else:
                            f = 8
                    dp[i+1][j or d < n[i]][k|f] += dp[i][j][k]
    ans = 0
    for i in range(2):
        ans += dp[l][i][7]
    print(ans)
#D
def D():
    def factorial(n):
        if n <= 3:
            return [n]
        l = []
        i = 2
        m = n
        while i**2 <= n:
            while m%i == 0:
                l.append(i)
                m //= i
            i += 1
        if m != 1:
            l.append(m)
        return l

    n = I()
    d = defaultdict(int)
    for i in range(2,n+1):
        l = factorial(i)
        for j in l:
            d[j] += 1
    a3 = 0
    a5 = 0
    a15 = 0
    a25 = 0
    a75 = 0
    for i in d.keys():
        if d[i] >= 74:
            a75 += 1
        if d[i] >= 24:
            a25 += 1
        if d[i] >= 14:
            a15 += 1
        if d[i] >= 4:
            a5 += 1
        if d[i] >= 2:
            a3 += 1
    ans = a75+(a3-1)*a25+(a5-1)*a15+(a3-2)*a5*(a5-1)//2
    print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
n = int(input())

soinsu_in_n = [0] * 50
seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
for i in range(1,n+1):
  a = i
  for j in seed_primes:
    while a%j == 0:
      a = a // j
      soinsu_in_n[j] += 1
    if a == 1:
      break

over74 = sum(item >= 74 for item in soinsu_in_n)
over24 = sum(item >= 24 for item in soinsu_in_n)
over14 = sum(item >= 14 for item in soinsu_in_n)
over4= sum(item >= 4 for item in soinsu_in_n)
over2= sum(item >= 2 for item in soinsu_in_n)

count = 0
# 74
if over74 >= 1:
  count += over74

# 24 2 or 2 24
if over24 >= 1:
  count += over24 * (over2 - over24)
if over14 >= 2:
  count += over24 * (over24 - 1)

# 14 4 or 4 14
if over14 >= 1:
  count += over14 * (over4 - over14)
if over14 >= 2:
  count += over14 * (over14-1)

# 442 or 424 or 244
if over4 >= 3:
  count += (over4) * (over4-1) * (over4-2) // 2
if over4 >= 2:
  count += (over4) * (over4-1) // 2 * (over2-over4)

print(count)

Submission status: Accepted

Solution code:
#ABC114 D
#N!の約数のうち, ちょうど約数を75個もつものは何個あるか?
#ただしNは1以上100以下
#
#愚直な方針1:
#Nを素因数分解する
#N!を素因数分解する
#それぞれの約数をDiとおき,Diの約数の個数を求める
#Diの約数の個数が75個であるものを数える
#
#考える(1):
#ある整数Mに対し,Mの約数の個数は?
#こたえはM=Π(pi**qi)と素因数分解できたとき,Π(qi+1)
#ところで75 = 3 * 5 * 5である
#つまり整数Mが約数を75個もつならば,Mの素因数分解は
#	M = p1**2 * p2**4 * p3**4
# M = p1**4 * p2**14
# M = p1**2 * p2**24
# M = p1**74
#のどれかになるはずである(各pの大小は問わない)
#
#
#愚直な方針2:
#Nを素因数分解する
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]
nprimes = {}
for prime in primes:
	nprimes[prime] = 0

#N!を素因数分解する
for N in range(int(input())):
	if N==0:
		continue
	else:
		M = N+1
		for prime in primes:
			if M < prime:
				break
			else:
				while True:
					if M % prime != 0:
						break
					else:
						M = int(M / prime)
						nprimes[prime] += 1

#N!を素因数分解した結果をΠ(pi**qi)とおく
#print(list(nprimes.values()))

#次の場合の数を合計する
#[1]M = p1**74 とするときの素数p1の選び方
#			これはqi>=74をみたすiの個数に等しい
#[2]M = p1**2 * p2**24 とするときの素数p1,p2の選び方
#			素数p2の選び方は, qi>=24をみたすiの個数に等しい
#		  素数p1の選び方は, qj>=2をみたすjの個数-1に等しい
#			よってこたえはこれら2つの積
#[3]M = p1**4 * p2**14 とするときの素数p1,p2の選び方
#			素数p2の選び方は, qi>=14をみたすiの個数に等しい
#		  素数p1の選び方は, qj>=4をみたすjの個数-1に等しい
#			よってこたえはこれら2つの積
#		  (qj>=4 であるすべてのj(ただしj!=i)に対して,qj-3の合計)
#[4]M = p1**2 * p2**4 * p3**4 とするときの素数p1,p2,p3の選び方
#			素数p2,p3の選び方は, qi>=4をみたすiの個数をIとするとI*(I-1)/2
#		  素数p1の選び方は, qj>=2をみたすjの個数-2に等しい
#			よってこたえはこれらの積
#
#準備として,
#qiが2-3であるiの個数をxとする
#qiが4-13であるiの個数をyとする
#qiが14-23であるiの個数をzとする
#qiが24-73であるiの個数をwとする
#qi>=74をみたすiの個数をvとする

nums = [0,0,0,0,0] #x,y,z,w,v

for i in list(nprimes.values()):
	if i >= 74:
		nums[4] += 1
	elif i >= 24:
		nums[3] += 1
	elif i >= 14:
		nums[2] += 1
	elif i >= 4:
		nums[1] += 1
	elif i >= 2:
		nums[0] += 1

x,y,z,w,v = nums

#[1]M = p1**74 とするときの素数p1の選び方
#			これはqi>=74をみたすiの個数に等しい
result = 0
result += v
#[2]M = p1**2 * p2**24 とするときの素数p1,p2の選び方
#			素数p2の選び方は, qi>=24をみたすiの個数に等しい
#		  素数p1の選び方は, qj>=2をみたすjの個数-1に等しい
#			よってこたえはこれら2つの積
result += (w+v)*(x+y+z+w+v-1)
#[3]M = p1**4 * p2**14 とするときの素数p1,p2の選び方
#			素数p2の選び方は, qi>=14をみたすiの個数に等しい
#		  素数p1の選び方は, qj>=4をみたすjの個数-1に等しい
#			よってこたえはこれら2つの積
#		  (qj>=4 であるすべてのj(ただしj!=i)に対して,qj-3の合計)
result += (z+w+v)*(y+z+w+v-1)
#[4]M = p1**2 * p2**4 * p3**4 とするときの素数p1,p2,p3の選び方
#			素数p2,p3の選び方は, qi>=4をみたすiの個数をIとするとI*(I-1)/2
#		  素数p1の選び方は, qj>=2をみたすjの個数-2に等しい
#			よってこたえはこれらの積
result += (y+z+w+v)*(y+z+w+v-1)*(x+y+z+w+v-2)/2
print(int(result))

Submission status: Accepted

Solution code:
import math
import random


class Prime:
    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
prime = Prime()
N = int(input())
def merge_dict_add_values(d1, d2):
    return dict(Counter(d1) + Counter(d2))
from collections import Counter
add_dict = {}
for i in range(N):
    add_dict = merge_dict_add_values(add_dict,prime.find_factors(i+1))
import numpy as np
a= np.array(list(add_dict.values()))
print(int((len(a[a>1])-2)*len(a[a>3])*(len(a[a>3])-1)/2)
      +int(len(a[a>=74]))
      +int(len(a[a>=24]))*(int(len(a[a>=2]))-1)
      +int(len(a[a>=14]))*(int(len(a[a>=4]))-1))

Submission status: Accepted

Solution code:
PRIME_NUMBER_U48 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]


def main():
    n = int(input())
    prime_counter = {p: 0 for p in PRIME_NUMBER_U48}
    for p in PRIME_NUMBER_U48:
        tmp = n
        while tmp > 0:
            tmp = tmp // p
            prime_counter[p] += tmp

    ans = 0
    for p in prime_counter:
        if prime_counter[p] >= 74:
            ans += 1
        if prime_counter[p] >= 24:
            for i in prime_counter:
                if i != p and prime_counter[i] >= 2:
                    ans += 1
        if prime_counter[p] >= 14:
            for i in prime_counter:
                if i != p and prime_counter[i] >= 4:
                    ans += 1

    two_or_three = [p for p in prime_counter if prime_counter[p] == 2 or prime_counter[p] == 3]
    over_three = [p for p in prime_counter if prime_counter[p] >= 4]
    tot_size = len(two_or_three)
    ot_size = len(over_three)
    if tot_size > 0 and ot_size >= 2:
        ans += tot_size * ot_size * (ot_size - 1) // 2
    if ot_size >= 3:
        ans += ot_size * (ot_size - 1) * (ot_size - 2) // 2

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# /user/bin/python
# -*- coding: utf-8 -*-
import sys 


N = int(input())

def fact(e, n):
  i = 2
  while(n > 1 and i <= n):
    if n % i == 0:
      n //= i
      if i in e:
        e[i] += 1
      else:
        e[i] = 1
    else:
      i += 1

def cnt75(elem_v, elem_75):
  ans = 1
  for i in range(len(elem_75)):
    n = 0
    for j in elem_v:
      if j >= elem_75[i]:
        n += 1
    ans *= (n-i)
  return ans    

def cnt75_2(elem_v):
  ans = 1
  n = 0
  m = 0
  for i in elem_v:
    if i >= 4:
      n += 1
    if i >= 2:
      m += 1
  return n*(n-1)//2 * (m-2)

elem = {}
for n in range(2, N+1):
  fact(elem, n)
elem_v = sorted(elem.values())

ans = cnt75(elem_v,[74])
ans += cnt75(elem_v,[24,2])
ans += cnt75(elem_v,[14,4])
ans += cnt75_2(elem_v)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

sosuu = []
for i in range(2, N + 1):
    flag = True
    for s in sosuu:
        if i % s == 0:
            flag = False
            break
    if flag:
        sosuu.append(i)

disolvers = [[], []]
for i in range(2, N + 1):
    ret = [0] * len(sosuu)
    t = i
    while t > 1:
        for i, s in enumerate(sosuu):
            if t % s == 0:
                t = t // s
                ret[i] += 1
                break
    disolvers.append(ret)

# 約数の数
# Nを素因数分解したときに、 n1 ** p1 * n2 ** p2 .... ni * pi とすると
# (p1 + 1) * (p2 + 1) * ... * (pi + 1) となる
# ここで 約数個数75 を分解すると 5, 5, 3
# つまり、数字M　は
#   素数1 ** 4 * 素数2 ** 4 * 素数3 ** 2
#   素数1 ** 24 * 素数2 ** 2
#   素数1 ** 14 * 素数3 ** 4
#   素数1 ** 75
# のいずれかで表せる必要がある

# 9! を素因数分解すると、 2**7, 3**4, 5 ** 1, 7 ** 1
#  > 上記の (4, 4, 2) を満たせない。
# 10! は、 2**8, 3**4, 5 ** 2, 7 ** 1
#  > (4, 4, 2) を満たすパターンが存在する  (2**4, 3**4, 5**2)

d_count = [0] * len(sosuu)
for i in range(2, N + 1):
    di = disolvers[i]
    for i, d in enumerate(di):
        d_count[i] += d

created_numbers = []
def count_numbers(depth, pow_count, used_idx, curr):
    if depth == len(pow_count):
        di = disolvers[N]
        t = 1
        for i in range(len(pow_count) - 1, -1, -1):
            idx = curr[i]
            t = t * (sosuu[idx] ** pow_count[i])
        if t in created_numbers:
            return 0
        created_numbers.append(t)
        return 1
    num = pow_count[depth]
    ret = 0
    for i in range(len(d_count)):
        n = d_count[i]
        if n >= num and i not in used_idx:
            u2 = used_idx + [i]
            ret += count_numbers(depth + 1, pow_count, u2, curr + [i])
    return ret

total = 0
total += count_numbers(0, [4, 4, 2], [], [])
total += count_numbers(0, [24, 2], [], [])
total += count_numbers(0, [14, 4], [], [])
total += count_numbers(0, [74], [], [])

print(total)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

def eratosthenes(n):
    p = [1]
    t = [True] * n

    t[1] = True
    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p


@mt
def slv(N):
    ps = eratosthenes(100)
    ps.pop(0)
    c = Counter()
    for i in range(2, N+1):
        n = i
        while n not in ps:
            for p in ps:
                if n % p == 0:
                    c[p] += 1
                    n //= p
                    break
        c[n] += 1

    c2 = len(list(filter( lambda x: x>=2, c.values())))
    c4 = len(list(filter( lambda x: x>=4, c.values())))
    c14 = len(list(filter( lambda x: x>=14, c.values())))
    c24 = len(list(filter( lambda x: x>=24, c.values())))
    c74 = len(list(filter( lambda x: x>=74, c.values())))
    ans = 0
    if c2 >= 3 and c4 >= 2:
        ans += (c4*(c4-1)//2) * (c2-2)
    if c4 > 0 and c14 > 0:
        ans += (c4-1) * c14
    if c2 > 0 and c24 > 0:
        ans += (c2-1) * c24
    if c74 > 0:
        ans += c74
    return ans


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

def eratosthenes(n):
    p = [1]
    t = [True] * n

    t[1] = True
    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p


@mt
def slv(N):
    ps = eratosthenes(100)
    ps.pop(0)
    c = Counter()
    for i in range(2, N+1):
        n = i
        while n not in ps:
            for p in ps:
                if n % p == 0:
                    c[p] += 1
                    n //= p
                    break
        c[n] += 1

    c2 = len(list(filter( lambda x: x>=2, c.values())))
    c4 = len(list(filter( lambda x: x>=4, c.values())))
    c14 = len(list(filter( lambda x: x>=14, c.values())))
    c24 = len(list(filter( lambda x: x>=24, c.values())))
    c74 = len(list(filter( lambda x: x>=74, c.values())))
    ans = 0
    if c2 >= 3 and c4 >= 2:
        ans += (c4*(c4-1)//2) * (c2-2)
    if c4 > 0 and c14 > 0:
        ans += (c4-1) * c14
    
    if c2 > 0 and c24 > 0:
        ans += (c2-1) * c24
    if c74 > 0:
        ans += c74
    return ans


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

N = int(input())

num = [0 for _ in range(N+1)]
for i in range(2, N+1):
    cur = i
    for j in range(2, i+1):
        while cur % j == 0:
            num[j] += 1
            cur //= j


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


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

Submission status: Accepted

Solution code:
N, = (int(x) for x in input().split())

n_prime = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

n_prime_sum = [0]*len(n_prime)
for n in range(1, N+1):
    for i, p in enumerate(n_prime):
        np = 0
        n_c = n
        while(n_c % p == 0):
            n_c = n_c // p
            np += 1
        n_prime_sum[i] += np

p_2 = len([0 for x in n_prime_sum if x >= 2])
p_4 = len([0 for x in n_prime_sum if x >= 4])
p_14 = len([0 for x in n_prime_sum if x >= 14])
p_24 = len([0 for x in n_prime_sum if x >= 24])
p_74 = len([0 for x in n_prime_sum if x >= 74])

n_75 = (p_2-p_4)*p_4*(p_4-1)//2 + p_4*(p_4-1)*(p_4-2)//2 + p_14*(p_4-1) + p_24*(p_2-1) + p_74
print(n_75)

Submission status: Accepted

Solution code:
def prime_fact(n: int) -> dict:
    ret = {}
    div = 2
    while n >= div:
        if n % div == 0:
            n //= div
            ret[div] = 1
        while n % div == 0:
            n //= div
            ret[div] += 1
        if div == 2:
            div += 1
        else:
            div += 2
    return ret


def fact(n: int) -> int:
    if n < 0:
        return -1
    if n == 0:
        return 1
    return n*fact(n-1)


def q756(N: int) -> int:
    f = fact(N)
    p = prime_fact(f)

    # それぞれ 74, 24, 14, 4, 2, 個以上の因数の数
    c74, c24, c14, c4, c2 = 0, 0, 0, 0, 0
    for v in p.values():
        if v >= 74:
            c74 += 1
        if v >= 24:
            c24 += 1
        if v >= 14:
            c14 += 1
        if v >= 4:
            c4 += 1
        if v >= 2:
            c2 += 1

    ret = c74
    if c2 > 1:
        ret += c24 * (c2-1)
    if c4 > 1:
        ret += c14 * (c4-1)
    if c2 > 2 and c4 > 1:
        ret += ((c4 * (c4-1)) // 2) * (c2-2)

    return ret


if __name__ == "__main__":
    N = int(input())
    ans = q756(N)
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
prits = [0 for i in range(n+1)]

for i in range(1,n+1):
    k = 2
    while k*k<=i:
        while i%k == 0:
            i = i//k
            prits[k] += 1
        k += 1
    if i>1 :
        prits[i] += 1
#print(prits)

a,b,c,d,e = [],[],[],[],[]

for i in range(len(prits)):
    num = prits[i]
    if num >=2:
        e.append(i)
    if num >=4:
        d.append(i)
    if num >=14:
        c.append(i)
    if num >=24:
        b.append(i)
    if num >=74:
        a.append(i)

#print(len(a),len(b),len(c),len(d),len(e))

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

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import itertools
N = int(input())
dic = defaultdict(int)
for i in range(2, N+1):
    for j in range(2, i + 1):
        while i % j == 0:
            i /= j
            dic[j] += 1
lst_2 = [k for k, v in dic.items() if v >= 2]
lst_4 = [k for k, v in dic.items() if v >= 4]
lst_14 = [k for k, v in dic.items() if v >= 14]
lst_24 = [k for k, v in dic.items() if v >= 24]
lst_74 = [k for k, v in dic.items() if v >= 74]
z = list(itertools.combinations(lst_4, 2))
p_2_q_4_r_4 = len([x for x in list(itertools.product(lst_2, z)) if x[0] != x[1][0] and x[0] != x[1][1]])
p_14_q_2 = len(lst_14) * len(lst_4) - len([x for x in lst_14 if x in lst_4])
p_2_q_24 = len(lst_2) * len(lst_24) - len([x for x in lst_2 if x in lst_24])
p_74 = len([k for k, v in dic.items() if v >= 74])
print(p_2_q_4_r_4 + p_14_q_2 + p_2_q_24 + p_74)

Submission status: Accepted

Solution code:
N = int(input())
def sieve(n):
    num = [True]*n
    num[0]=num[1]= False
    for i in range(int(n**0.5)+1):
        if num[i]:
            for j in range(i**2,n,i):
                num[j] = False
    return ([i for i in range(2,n) if num[i]])
s = sieve(100)
fact = [[i,0] for i in s]
for i in range(2,N+1):
    j = i
    for m in range(len(s)):
        if j == 1:
            break
        while j % s[m] == 0:
            j = j // s[m]
            fact[m][1] += 1

factor_num = [i[1] for i in fact]
def multi_index(l, x): # l中のxのindexのlistを返す
    return [i for i, _x in enumerate(l) if _x >= x]
n75 = 0
if sum([1 for i in factor_num if i >= 4]) >= 2:
    over4 = multi_index(factor_num,4)
    over2 = multi_index(factor_num,2)
    for i in range(len(over4)):
        for j in range(i,len(over4)):
            for k in range(len(over2)):
                if i!=j and over4[i]!=over2[k] and over4[j]!=over2[k]:
                    n75 += 1
    try:
        over24 = multi_index(factor_num,24)
        for i in over24:
            for j in over2:
                if i!= j:
                    n75 += 1
    except:
        pass

    try:
        over14 = multi_index(factor_num,14)
        for i in over14:
            for j in over4:
                if i != j:
                    n75 += 1
    except:
        pass

    try:
        over74 = multi_index(factor_num,74)
        n75 += len(over74)
    except:
        pass
print(n75)

Submission status: Accepted

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
INF = 10**18

N=ri()
pri = [0]*101

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

exp = []
for i in range(101):
    if pri[i] > 0:
        exp += [pri[i] + 1]

exp.sort()
exp_len = len(exp)
import bisect
cnt_75 = exp_len - bisect.bisect_left(exp,75)
cnt_25 = exp_len - bisect.bisect_left(exp,25)
cnt_15 = exp_len - bisect.bisect_left(exp,15)
cnt_5 = exp_len - bisect.bisect_left(exp,5)
cnt_3 = exp_len - bisect.bisect_left(exp,3)
ans = 0

ans += cnt_75
ans += cnt_25*cnt_3 - cnt_25
ans += cnt_15*cnt_5 - cnt_15
ans += cnt_5*(cnt_5-1)/2*cnt_3 - cnt_5*(cnt_5-1)/2*2
ans = int(ans)

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
# 素因数分解
# 戻り値: リスト
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass

yakusu = []
n = int(input())
for i in range(1, n+1):
    yakusu += prime_factor(i)
c = Counter(yakusu)
d = {}
for ik, iv in c.items():
    for jk, jv in c.items():
        for kk, kv in c.items():
            if len(set([ik, jk, kk])) != 3:
                continue
            if iv >= 74:
                d[ik**74] = 0
            if iv >= 24 and jv >= 2:
                d[(ik**24)*(jk**2)] = 0
            if iv >= 14 and jv >= 4:
                d[(ik**14)*(jk**4)] = 0
            if iv >= 4 and jv >= 4 and kv >= 2:
                d[(ik**4)*(jk**4)*(kk**2)] = 0
print(len(d.values()))

Submission status: Accepted

Solution code:
n = int(input())

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

e = [0 for _ in range(n + 1)]

for i in range(2, n + 1):
    temp = i
    for j in range(2, i + 1):
        while temp % j == 0:
            e[j] += 1
            temp //= j

a = [0 for _ in range(75)]
for i in range(n + 1):
    for j in range(min(75, e[i] + 1)):
        a[j] += 1

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

Submission status: Accepted

Solution code:
#i!/usr/bin/env python
# coding: utf-8

from collections import Counter
import sys
input = sys.stdin.readline

def divisors(n):
    ret = {}
    tmp = n
    for p in [2, 3, 5, 7]:
        d = 0
        while tmp % p == 0:
            tmp /= p
            d += 1
        if d > 0:
            ret[p] = d
    if tmp > 1:
        ret[int(tmp)] = 1
    return ret


def main():
    patterns = [(5, 5, 3), (15, 5), (25, 3), (75)]
    N = int(input())
    divs = Counter()
    for n in range(1, N+1):
        divs.update(divisors(n))
    l = [0] * 5
    for i, p75 in enumerate([75, 25, 15, 5, 3]):
        for p, cnt in divs.most_common():
            if cnt >= p75-1:
                l[i] += 1
    ret = 0
    ret += l[0] # 75
    ret += l[1] * (l[4]-1) # 25 * 3
    ret += l[2] * (l[3]-1) # 15 * 5
    ret += (l[3] * (l[3]-1) / 2) * (l[4]-2) # 5 * 5 * 3
    print(int(ret))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
from collections import Counter
c = Counter()
for i in range(1,n+1):
    for j in range(2, i+1):
        while i % j == 0:
            c[j] += 1
            i //= j

def num(a):
    ret = 0
    for key, value in c.items():
        if value >= a:
            ret += 1
    return ret

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

Submission status: Accepted

Solution code:
from collections import Counter
def facrorize(n):
    c = Counter()
    t = 2
    while t**2 <= n:
        if n%t:
            t += 1
            continue
        while not n%t:
            c[t] += 1
            n //= t
    if n > 1:
        c[n] += 1
    return c

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

n = int(input())
d = Counter()
for i in range(1, n+1):
    c = facrorize(i)
    for key, value in c.items():
        d[key] += value

e = {2:[],4:[],14:[],24:[],74:[]}
for key, value in d.items():
    for cnt in e:
        if value >= cnt:
            e[cnt].append(key)

ans = 0
# 3, 5, 5 → 2, 4, 4
for two in e[2]:
    if two not in e[4]:
        ans += comb(len(e[4]), 2)
    else:
        ans += comb(len(e[4])-1, 2)
    # 3, 25 → 2, 24
    if two not in e[24]:
        ans += len(e[24])
    else:
        ans += comb(len(e[24])-1,1)

# 5, 15 → 4, 14
for four in e[4]:
    if four not in e[14]:
        ans += len(e[14])
    else:
        ans += comb(len(e[14]) - 1, 1)
# 75 → 74
ans += len(e[74])
print(ans)