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:
# Title: count all Shichi-Go numbers in N!
# Link: https://abc114.contest.atcoder.jp/tasks/abc114_d

import sys
import collections

sys.setrecursionlimit(10 ** 6)


read_single_int = lambda: int(sys.stdin.readline().strip())


def add_power(n: int, ps: list):
    i = 2
    while n != 1:
        if n % i == 0:
            n = n // i
            ps[i] += 1
        else:
            i += 1


def solution(n: int):
    ps = [0 for _ in range(n+1)]

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

    powers = collections.defaultdict(lambda: 0)

    for p in range(2, n+1):
        powers[p] = len(list(filter(lambda x: x >= p, ps)))

    return powers[74] + powers[24] * (powers[2]-1) + powers[14] * (powers[4]-1) + powers[4] * (powers[4]-1) * (powers[2]-2)//2


def main():
    n = read_single_int()
    print(solution(n))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
primes = [0 for i in range(n)]
for i in range(2, n+1):
    tmp = i
    for j in range(2, i+1):
        while(tmp % j == 0):
            primes[j-1] += 1
            tmp = tmp // 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:
n = int(input())
e = [0 for i in range(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:
N = int(input())

nums = list(range(1, N+1))
factors = []
for i, n in enumerate(nums):
    if n > 1:
        count = 0
        for j in range(i, len(nums)):
            while nums[j] % n == 0:
                nums[j] //= n
                count += 1
        factors.append((n, count))

f74 = len([True for n, k in factors if k >= 74])
f24 = len([True for n, k in factors if k >= 24])
f14 = len([True for n, k in factors if k >= 14])
f4 = len([True for n, k in factors if k >= 4])
f2 = len([True for n, k in factors if k >= 2])
print(f74 + f24 * (f2 - 1) + f14 * (f4 - 1) + f4 * (f4 - 1) // 2 * (f2 - 2))

Submission status: Accepted

Solution code:
N = int(input())

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

xs = {}

for n in range(2, N+1):
    for p in PRIMES:
        while n % p == 0:
            n //= p
            xs[p] = xs.get(p, 0) + 1
        if n == 1:
            break

vs = xs.values()

u74 = sum(v >= 74 for v in vs)
u24 = sum(v >= 24 for v in vs)
u14 = sum(v >= 14 for v in vs)
u4 = sum(v >= 4 for v in vs)
u2 = sum(v >= 2 for v in vs)

result = 0

# 75
if u74 >= 1:
    result += u74

# 25 * 3
if u24 >= 1 and u2 - 1 >= 1:
    result += u24 * (u2 - 1)

# 15 * 5
if u14 >= 1 and u4 - 1 >= 1:
    result += u14 * (u4 - 1)

# 5 * 5 * 3
if u4 >= 2 and u2 - 2 >= 1:
    result += u4 * (u4 - 1) // 2 * (u2 - 2)

print(result)

Submission status: Accepted

Solution code:
N = int(input())

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

xs = {}

for n in range(2, N+1):
    for p in PRIMES:
        while n % p == 0:
            n //= p
            xs[p] = xs.get(p, 0) + 1
        if n == 1:
            break

vs = sorted(xs.values())

u74 = sum(v >= 74 for v in vs)
u24 = sum(v >= 24 for v in vs)
u14 = sum(v >= 14 for v in vs)
u4 = sum(v >= 4 for v in vs)
u2 = sum(v >= 2 for v in vs)

# print(u74, u24, u14, u4, u2)

def nCr(n, r):
    result = 1
    for i in range(n - r + 1, n + 1):
        result *= i
    for i in range(1, r + 1):
        result //= i
    # print("nCr", n, r, result)
    return result

result = 0

# 75
result += u74

# 25 * 3
if u24 >= 1 and u2 - u24 >= 1:
    result += nCr(u24, 1) * nCr(u2 - 1, 1)

# 15 * 5
if u14 >= 1 and u4 - u14 >= 1:
    result += nCr(u14, 1) * nCr(u4 - 1, 1)

# 5 * 5 * 3
if u4 >= 2 and u2 - u4 >= 1:
    result += nCr(u4, 2) * nCr(u2 - 2, 1)

print(result)

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
sosu = [2]
import math

for i in range(3,101):
    fl = True
    for j in sosu:
        if j > math.sqrt(i):
            break
        if i % j == 0:
            fl = False
            break
    if fl:
        sosu.append(i)
# print(sosu)

def getpow(n, x):
    if n >= x:
        return 1 + getpow(n/x, x) if n % x == 0 else 0
    else:
        return 0

has = {}
powlist = []


for i in range(1,N+1):
    for p in sosu:
        if p > i:
            break
        if i % p == 0:
            has[p] = 2 if not p in has else has[p] + getpow(i,p)
            # print("p: {}".format(p))


# print(has)


def f(primes, num):
    if num == 1:
        # print("\t end: {}".format(primes))
        return 1
    else:
        sum = 0
        for e,p in enumerate(primes.keys()):
            for i in range(3, primes[p]+1):
                if num // i >= 1 and num % i == 0:
                    prime2 = primes.copy()
                    try:
                        # prime2[p] = prime2[p] - i
                        prime2[p] = 0
                    except:
                        print(prime2,e,p)
                        exit(1)
                    # print("num: {}, i: {},  {} => {}".format(num,i,primes,(prime2)))
                    sum += f(prime2, num//i)
        return sum
            

num75 = 0
num25 = 0
num15 = 0
num5  = 0
num3 = 0
# primes = has
primes = []
for p in has:
    primes.append(has[p])
def num(m):
    return len(
        list(
            filter(
                lambda x: 
                    x >=  m, primes
            )
        )
    )
    
# print(num(5), num(3), list(filter(lambda x: x >= 3, primes)))
# sum = f(has, 75)
# print(sum // 6)
sum = num(75) + num(25) * (num(3)-1) + num(15) * (num(5) - 1) + num(5) * (num(5)-1) * (num(3)-2) // 2
print(sum)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

cnt = 0

for i in range(2, N+1):
    for j in range(i+1, N+1):
        for k in range(2, N+1):
            if i == j or j == k or k == i:
                continue
            if e[i] >= 4 and e[j] >= 4 and e[k] >= 2:
                cnt += 1

for i in range(2, N+1):
    for j in range(2, N+1):
        if i == j or j == k or k == i:
            continue
        if e[i] >= 14 and e[j] >= 4:
            cnt += 1

for i in range(2, N+1):
    for j in range(2, N+1):
        if i == j or j == k or k == i:
            continue
        if e[i] >= 24 and e[j] >= 2:
            cnt += 1

for i in range(2, N+1):
    if e[i] >= 74:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())

primes = []
def prime():
    global primes
    primes = []
    for i in range(2,100):
        p = True
        for j in primes:
            if i % j == 0:
                p = False
                break
        if p:
            primes.append(i)

hash = {}
prime()

for i in range(1, n+1):
    k = i
    for j in primes:
        if k % j == 0:
            while k % j == 0:
                if j in hash:
                    hash[j] += 1
                else:
                    hash[j] = 1
                k = k // j
a = 0
b = 0
c = 0
d = 0
e = 0
for k, v in hash.items():
    if v >= 4:
        a += 1
    if v >= 2:
        b += 1
    if v >=14:
        c += 1
    if v >= 24:
        d += 1
    if v >= 74:
        e += 1

total = 0
if a<2 or b<3:
    print(0)
else:
    total = a*(a-1)*(b-2) // 2 + c *  (a-1) + d * (b-1) + e
    print(total)

Submission status: Accepted

Solution code:
n=int(input())
d=dict()
for m in range(1,n+1):
    while m>1:
        for i in range(2,int(m**0.5)+1):
            if m%i==0:break
        else:i=m
        d[i]=d.get(i,0)+1
        m/=i
def num(n):
    return len(list(filter(lambda x:x>=n,d.values())))

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

Submission status: Accepted

Solution code:
N, = map(int, raw_input().split())
p = {}
for i in range(2, N+1):
  ii = i
  for j in range(2, i+1):
    while(ii%j==0):
      p[j] = p.get(j, 0)+1
      ii //= j
m = [3,5,15,25,75]
x = {}
for l in m:
  x[l-1] = 0
for k in p:
  for l in m:
    if p[k]>=l-1:
      x[l-1] += 1
r = 0
if x[4]>=2 and x[2]-2>=1:
  r += x[4]*(x[4]-1)*(x[2]-2)//2
if x[14]>=1 and x[4]-1>=1:
  r += x[14]*(x[4]-1)
if x[24]>=1 and x[2]-1>=1:
  r += x[24]*(x[2]-1)
if x[74]>=1:
  r += x[74]
print r

Submission status: Accepted

Solution code:
import math

prime = [2,3,5,7,11]
for i in range(13,53,2):
    for j in [3,5,7]:
        if i%j == 0:
            break
    else:
        prime.append(i)

num75 = [2**74]
for i in [2,3,5]:
    tmp = i**24
    for j in prime:
        if i==j:
            continue
        num75.append(tmp*j*j)

for i in [2,3,5,7]:
    tmp = i**14
    for j in prime:
        if i==j:
            continue
        num75.append(tmp*(j**4))

for i in [2,3,5,7,11,13,17,19,23]:
    for j in [2,3,5,7,11,13,17,19,23]:
        if j<=i:
            continue
        for k in prime:
            if (i==k)or(j==k):
                continue
            num75.append((i**4)*(j**4)*(k**2))


N = int(input())
f = math.factorial(N)
ans = 0
for i in num75:
    if f%i == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
from collections import defaultdict

input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


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


N = int(input())

prime_cnt = defaultdict(int)
for n in range(N):
    n += 1
    i = 2
    while i * i <= n:
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            prime_cnt[i] += cnt
        i += 1

    if n != 1:
        # nに素数が残っている場合処理をする
        prime_cnt[n] += 1


def num(n):
    cnt = 0
    for key in prime_cnt.keys():
        if prime_cnt[key] >= n - 1:
            cnt += 1

    return cnt


# 75 -> 3*5*5, 3*25, 5*15, 75
# 2^4*3^4*5^2と3^4*2^4*5^2は同じ，(重複の数)!で割る
print(num(75) + num(15) * (num(5) - 1) + num(25) * (num(3) - 1)
      + num(5) * (num(5) - 1) * (num(3) - 2) // 2)

Submission status: Accepted

Solution code:
n = int(input())
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        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]] #n番目までの素数のリストを生成
prime = primes(100)
primeCount = [0 for i in range(25)]

def searchSingle():
    res = 0
    for i in range(len(primeCount)):
        if primeCount[i] >= 74:
            res += 1
    return res

def searchDouble():
    res = 0
    for i in range(len(primeCount)):
        for j in range(len(primeCount)):
            cnt_i = primeCount[i]
            cnt_j = primeCount[j]
            if cnt_i >= 14 and cnt_j >= 4 and i != j:
                res += 1
            if cnt_i >= 24 and cnt_j >= 2 and i != j:
                res += 1
    return res

def searchTriple():
  res=0
  for i in range(len(primeCount)):
    for j in range(len(primeCount)):
      for k in range(j+1,len(primeCount)):
        if primeCount[i] >=2 and primeCount[j] >=4 and primeCount[k] >=4 and i!=j and j!=k and i!=k:
          res+=1
  return res

for i in range(2, n+1):
    cnt=i
    for j in range(len(prime)):
        if cnt % prime[j] == 0:
            while cnt % prime[j] == 0:
                cnt//= prime[j]
                primeCount[j] += 1
print(searchSingle() + searchDouble() + searchTriple())

Submission status: Accepted

Solution code:
N = int(input())

def decompose(n):
    prime_exp = [0] * (n+1)
    for i in range(2, n+1):
        exponent = 0
        while(n % i == 0):
            n /= i
            exponent += 1
        if exponent != 0:
            prime_exp[i] = exponent
    return prime_exp

def decompose_fact(n):
    prime_exp = [0] * (n+1)
    for i in range(2, n+1):
        for j, k in enumerate(decompose(i)):
            prime_exp[j] += k
    return prime_exp

def solve(n):
    ans = 0
    dec_f = decompose_fact(n)
    for i in range(n+1):
        if dec_f[i] >= 74:
            ans += 1

    for i in range(n+1):
        for j in range(n+1):
            if i != j and (dec_f[i] >= 2 and dec_f[j] >= 24):
                ans += 1

    for i in range(n+1):
        for j in range(n+1):
            if i != j and (dec_f[i] >= 4 and dec_f[j] >= 14):
                ans += 1

    for i in range(n+1):
        for j in range(n+1):
            for k in range(n+1):
                if i != j and i != k and j != k and j < k and (dec_f[i] >= 2 and dec_f[j] >= 4 and dec_f[k] >= 4):
                    ans += 1
    return ans

print(solve(N))

Submission status: Accepted

Solution code:
import collections
import itertools

yakusuu = {}
for j in range(2, 101):
    I = j
    s = 0
    R = int(I)
    L = []
    while s == 0:
        for i in range(2, R + 1):
            if I % i == 0:
                I = I / i
                if I == 1:
                    s = 1
                L.append(i)
                break
    if len(L) == 1:
        yakusuu[R] = [R]
    else:
        yakusuu[R] = L

n = int(input())

cnt = 0

for num in range(1, n + 1):
    tmp = []
    if n == 1:
        print(0)
        exit()
    for i in range(2, num + 1):
        tmp += yakusuu[i]

tmp = dict(collections.Counter(tmp))
tmp_array = sorted(list(tmp.keys()))

cnt = 0

for i in tmp_array:
    if tmp[i] >= 74:
        cnt += 1

for i in tmp_array:
    for j in tmp_array:
        if i == j:
            continue
        elif tmp[i] >= 14 and tmp[j] >= 4:
            cnt += 1

for i in tmp_array:
    for j in tmp_array:
        if i == j:
            continue
        elif tmp[i] >= 24 and tmp[j] >= 2:
            cnt += 1

res_array = list(itertools.combinations(tmp_array, 3))
for i in range(len(tmp_array)):
    for j in range(len(tmp_array)):
        for k in range(j+1, len(tmp_array)):
            if (j == i) or (i == k): continue
            if tmp[tmp_array[i]] >= 2 and tmp[tmp_array[j]] >= 4 and tmp[tmp_array[k]] >= 4:
                cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())

factor = [0 for _ in range(N + 1)]

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


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

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

Submission status: Accepted

Solution code:
def main():
    """
    input:
        1 <= N <= 100

    output:
        N! の約数のうち、七五数 は何個
        七五数とは約数をちょうど 75個持つ正の整数
    """
    N = int(input())

    ans = f(N)
    print(ans)


def f(N):
    """素因数分解までは浮かんだ
    """
    factor_all = [[] for _ in range(N + 1)]
    factors = [0] * (N + 1)
    for i in range(2, N + 1):
        # N_max=100 より √i にしなくても高速なので簡易に実装
        x = i
        for div in range(2, x + 1):
            while x % div == 0:
                factors[div] += 1
                factor_all[i].append(div)
                x //= div

    # print(factors)
    # print(factor_all)
    ans1 = editorial(factors)
    ans2 = ref(factors)
    assert ans1 == ans2

    return ans1


def editorial(factors):
    factors = factors

    def a(x):
        n = 0
        for f in factors:
            if f >= x - 1:
                n += 1

        return n

    # どういうこと？
    # 75: 1つの素数で0~74乗なのでわかる
    # -1: => 0乗は1だから、他のパターンでも起こるので除外？
    # 75,
    ans = a(75)
    ans += a(25) * (a(3) - 1)
    ans += a(15) * (a(5) - 1)
    ans += a(5) * (a(5) - 1) * (a(3) - 2) // 2

    return ans


def ref(factors):
    """https://beta.atcoder.jp/contests/abc114/submissions/3704878
    """
    # 2以上の理由: n=1ではその数字は素数なので約数が1と自信しかないので意味がない
    # a^1 * b^2 * c^3: 1*2*3=6通り と使っても約数の数が変わらない
    nums = [n for n in factors if n >= 2]

    # 75 の約数
    divs = [i for i in range(1, 75+1) if 75 % i == 0]

    # dp[i][j]
    # i: 1-index baseで nums[1]...nums[n]までの n種類の素因数についてi番目まで利用
    # j: 約数の数0-75 まで
    # どんな数でも1では割れるので1, 1は素数に含めない
    n_nums = len(nums)
    dp = [[0] * (75 + 1) for _ in range(n_nums + 1)]
    dp[0][1] = 1

    # 75個なので,75の約数の組合せでしか割れないのは分かるが
    # 2重ループでよいのか？: [1, 3. 15, 25, 75]
    from itertools import product
    div_pairs = [(d1, d2)
                 for d1, d2 in product(divs, repeat=2)
                 if d1 * d2 <= 75]

    for i in range(n_nums):
        for d1, d2 in div_pairs:
            # TODO: 75 = 3^1 * 5^2, そもそも 3*15=3^2*5, 3*3, は必要なのか？
            if d1 * d2 in (45, 9):
                continue

            # 遷移
            # i−1 番目の素因数まででできた約数が d1 個で、
            # i 番目の素因数を d2−1 個選ぶ、という選び方
            # => editorial 内の a func の f >= x - 1 と同じ

            # nums[i] + 1 >= d2: より下記のほうが意味がわかりそう
            if nums[i] >= d2 - 1:
                # print(i, nums[i], (d1, d2), d1 * d2,
                #       dp[i][d1], dp[i+1][d1 * d2], sep="\t")
                dp[i+1][d1 * d2] += dp[i][d1]

    ans = dp[n_nums][75]
    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def D():
    N = int(input())
    numberlist = [0 for i in range(N + 1)]
    for i in range(1, N + 1):
        tmp = i
        for j in range(2, i + 1):
            while tmp % j == 0:
                numberlist[j] += 1
                tmp /= j
    anslist = []
    for p in range(N + 1):
        if numberlist[p] + 1 >= 75:
            anslist.append(pow(p, 74))
        for q in range(N + 1):
            if p != q and numberlist[p] + 1 >= 15 and numberlist[q] + 1 >= 5:
                anslist.append(pow(p, 14) * pow(q, 4))
            if p != q and numberlist[p] + 1 >= 25 and numberlist[q] + 1 >= 3:
                anslist.append(pow(p, 24) * pow(q, 2))
            for r in range(N + 1):
                if p != q and q != r and r != p and numberlist[p] + 1 >= 5 and numberlist[q] + 1 >= 5 and numberlist[r] + 1 >= 3:
                    anslist.append(pow(p, 4) * pow(q, 4) * pow(r, 2))
    ans = 1
    anslist.sort()
    for i in range(1, len(anslist)):
        if anslist[i] != anslist[i - 1]:
            ans += 1
    if len(anslist) == 0:
        ans = 0
    print(ans)
D()

Submission status: Accepted

Solution code:
import collections
import itertools

prime = [2]
for i in range(3,100):
    check = True
    for k in range(2,i):
        if i%k == 0:
            check = False
    if check:
        prime.append(i)

def factorial(n):
    ans = []
    start = 0
    while n != 1:
        if n%prime[start] == 0:
            n = n//prime[start]
            ans.append(prime[start])
        else:
            start += 1
    return ans

n = int(input())
factor = [i for i in range(1,n+1)]
a = collections.Counter(factor)

for i in a:
    if i not in prime:
        temp = factorial(i)
        for k in range(len(temp)):
            a[temp[k]] += 1
        a[i] = 0

test = []
for i in a:
    if a[i] >= 2:
        test.append(i)
counter = 0
look2 = list(itertools.permutations(test,2))
look3 = list(itertools.permutations(test,3))

for i in range(len(test)):
    if a[test[i]] >= 74:
        counter += 1

for i in range(len(look2)):
    if a[look2[i][0]] >= 2 and a[look2[i][1]] >= 24:
        counter += 1
    if a[look2[i][0]] >= 4 and a[look2[i][1]] >= 14:
        counter += 1

for i in range(len(look3)):
    if a[look3[i][0]] >= 2 and a[look3[i][1]] >= 4 and a[look3[i][2]] >= 4 and look3[i][1] < look3[i][2]:
        counter += 1

print(counter)

Submission status: Accepted

Solution code:
import math
n=int(input())
ans=0
tmp=[0 for i in range(n+1)]
for i in range(2,n+1):
    now=i
    for j in range(2,n+1):
        while now%j==0:
            tmp[j]+=1
            now//=j
def solve(x):
    tmp1=len(list(filter(lambda y:y>=x-1,tmp)))
    return tmp1
print(solve(75)+solve(25)*(solve(3)-1)+solve(15)*(solve(5)-1)+
solve(5)*(solve(5)-1)*(solve(3)-2)//2)

Submission status: Accepted

Solution code:
n = int(input())
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
primeCount = [0 for i in range(25)]

def searchSingle():
    res = 0
    for i in range(len(primeCount)):
        if primeCount[i] >= 74:
            res += 1
    return res

def searchDouble():
    res = 0
    for i in range(len(primeCount)):
        for j in range(len(primeCount)):
            cnt_i = primeCount[i]
            cnt_j = primeCount[j]
            if cnt_i >= 14 and cnt_j >= 4 and i != j:
                res += 1
            if cnt_i >= 24 and cnt_j >= 2 and i != j:
                res += 1
    return res

def searchTriple():
  res=0
  for i in range(len(primeCount)):
    for j in range(len(primeCount)):
      for k in range(j+1,len(primeCount)):
        if primeCount[i] >=2 and primeCount[j] >=4 and primeCount[k] >=4 and i!=j and j!=k and i!=k:
          res+=1
  return res

for i in range(2, n+1):
    cnt=i
    for j in range(len(prime)):
        if cnt % prime[j] == 0:
            while cnt % prime[j] == 0:
                cnt//= prime[j]
                primeCount[j] += 1
print(searchSingle() + searchDouble() + searchTriple())

Submission status: Accepted

Solution code:
def D():
    N = int(input())
    tmplist = [0 for i in range(N + 1)]
    for i in range(1, N + 1):
        key = i
        for j in range(2, key + 1):
            while i % j == 0:
                tmplist[j] += 1
                i /= j
    ans = 0
    anslist = []
    for p in range(N + 1):
        if tmplist[p] + 1 >= 75:
            anslist.append(pow(p, 74))
        for q in range(N + 1):
            if p != q and tmplist[p] + 1 >= 25 and tmplist[q] + 1 >= 3:
                anslist.append(pow(p, 24) * pow(q, 2))
            if p != q and tmplist[p] + 1 >= 15 and tmplist[q] + 1 >= 5:
                anslist.append(pow(p, 14) * pow(q, 4))
            for r in range(N + 1):
                if p != q and q != r and r != p and tmplist[p] + 1 >= 5 and tmplist[q] + 1 >= 5 and tmplist[r] + 1 >= 3:
                    anslist.append(pow(p, 4) * pow(q, 4) * pow(r, 2))
    anslist.sort()
    ans = 1
    for i in range(1, len(anslist)):
        if anslist[i] != anslist[i - 1]:
            ans += 1
    if len(anslist) == 0:
        ans = 0
    print(ans)

D()

Submission status: Accepted

Solution code:
N=int(input())
prime=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
primeCount=[0 for i in range(25)]

def searchSingle():
  res=0
  for i in range(len(primeCount)):
    if primeCount[i] >= 74:
      res+=1
  return res

def searchDouble():
  res=0
  for i in range(len(primeCount)):
    for j in range(len(primeCount)):
      cnt_i=primeCount[i]
      cnt_j=primeCount[j]
      if cnt_i >= 14 and cnt_j >= 4 and i != j:
        res+=1
      if cnt_i >=24 and cnt_j >=2 and i!=j:
        res+=1
  return res

def searchTriple():
  res=0
  for i in range(len(primeCount)):
    for j in range(len(primeCount)):
      for k in range(j+1,len(primeCount)):
        if primeCount[i] >=2 and primeCount[j] >=4 and primeCount[k] >=4 and i!=j and j!=k and i!=k:
          res+=1
  return res

for i in range(2,N+1):
  cnt=i
  for j in range(len(prime)):
    if cnt % prime[j] == 0:
      while cnt % prime[j] == 0:
        cnt//=prime[j]
        primeCount[j]+=1
        
print(searchSingle() + searchDouble() + searchTriple())

Submission status: Accepted

Solution code:
def find_prime(n):
    e = [0] * (n + 1)
    for tmp in range(2, n + 1):
        i = 2
        while(tmp != 1):
            if tmp % i == 0:
                tmp //= i
                e[i] += 1
            else:
                i += 1

    return(e)


def num(i):
    return len(list(filter(lambda x: x >= i, e)))


n = int(input())

e = find_prime(n)
# print(e)

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

Submission status: Accepted

Solution code:
n = int(input())


# 入力 : 自然数     ex) 12
# 出力 : 約数リスト ex) [(2,2),(3,1)]
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


divList = [0 for i in range(n + 1)]
# divList[1] = 1
for i in range(2, n + 1):
    tmp = factorize(i)
    for j in range(len(tmp)):
        divList[tmp[j][0]] += tmp[j][1]
# print(divList)
# print(sum())
count = 0

# a^d * b^e * c^fの約数は(d+1)*(e+1)*(f+1)個
# つまり75個約数があるとは
# 3*5*5=(2+1)*(4+1)*(4+1)
# 3*25=(2+1)*(24+1)
# 5*15=(4+1)*(14+1)
# 75=(74+1)
# よって各約数を数えればいいだけ
for i in range(len(divList) - 2):
    for j in range(i + 1, len(divList) - 1):
        for k in range(j + 1, len(divList)):
            if divList[i] >= 2 and divList[j] >= 4 and divList[k] >= 4:
                # print("i:{} j:{} k:{} sum:{}".format(i, j, k, (i ** 2) * (j ** 4) * (k ** 4)))
                count += 1
            if divList[i] >= 4 and divList[j] >= 2 and divList[k] >= 4:
                # print("i:{} j:{} k:{} sum:{}".format(i, j, k, (i ** 4) * (j ** 2) * (k ** 4)))
                count += 1
            if divList[i] >= 4 and divList[j] >= 4 and divList[k] >= 2:
                # print("i:{} j:{} k:{} sum:{}".format(i, j, k, (i ** 4) * (j ** 4) * (k ** 2)))
                count += 1
for i in range(len(divList) - 1):
    for j in range(i + 1, len(divList)):
        if (divList[i] >= 2 and divList[j] >= 24):
            # print("i:{} j:{} sum:{}".format(i, j, (i ** 2) * (j ** 24)))
            count += 1
        if (divList[i] >= 24 and divList[j] >= 2):
            # print("i:{} j:{} sum:{}".format(i, j, (i ** 24) * (j ** 2)))
            count += 1
        if (divList[i] >= 14 and divList[j] >= 4):
            # print("i:{} j:{} sum:{}".format(i, j, (i ** 14) * (j ** 4)))
            count += 1
        if divList[i] >= 4 and divList[j] >= 14:
            # print("i:{} j:{} sum:{}".format(i, j, (i ** 4) * (j ** 14)))
            count += 1
for i in range(len(divList)):
    if divList[i] >= 74:
        # print("i:{} sum:{}".format(i, (i ** 74)))
        count += 1
print(count)

Submission status: Accepted

Solution code:
ps = [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]
N = int(input())
if N == 1:
  print(0)
  quit()
l = [0 for _ in range(98)]
def fac(n):
  for k in ps:
   if n == 1:
     break
   if n % k == 0:
    l[k] += 1
    fac(n // k)
    break

for i in range(2,N+1):
  fac(i)

p = [k for k in l if k > 1]

ans = 0

def num(n):
  r = 0
  for k in p:
    if k >= n:
      r += 1
  return(r)

if p[0] >= 74:
  ans += 1

#5*15

ans += (num(14) * (num(14) - 1))
ans += (num(14) * (num(4) - num(14)))

#3 * 25
ans += (num(24) * (num(24) - 1))
ans += (num(24) * (num(2) - num(24)))

#3 * 5 * 5
ans += (num(4) * (num(4) - 1) * (num(4) - 2) // 2)
ans += (num(4) * (num(4) - 1) //2) * (num(2) - num(4))

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = input()
cnt = [1] * 110
for num in range(1, N + 1):
    for i in range(2, 100):
        while num % i == 0:
            cnt[i] += 1
            num /= i

ans = 0
for i in range(N + 1):
    for j in range(N + 1):
        for k in range(N + 1):
            if i == j or j == k or k == i:
                continue
            if cnt[i] >= 3 and cnt[j] >= 5 and cnt[k] >= 5:
                ans += 1

ans /= 2

for i in range(N + 1):
    for j in range(N + 1):
        if i == j:
            continue
        if cnt[i] >= 5 and cnt[j] >= 15:
            ans += 1
        if cnt[i] >= 3 and cnt[j] >= 25:
            ans += 1
    if cnt[i] >= 75:
        ans += 1

print ans

Submission status: Accepted

Solution code:
import bisect
n = int(input())
if n == 1:
    print(0)
else:
    #nの素因数分解(O(n**0.5)
    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
    
    p = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
    r = [0] * 25 #n!を因数分解した時の各素数の数
    
    #n!の因数分解
    for i in range(2,n+1):
        k = 0
        while i != 1:
            while i%p[k] == 0:
                i = i //p[k]
                r[k] += 1
            k += 1
    
    r.sort()
    c75 = bisect.bisect_left(r,74)
    c25 = bisect.bisect_left(r,24)
    c15 = bisect.bisect_left(r,14)
    c5 = bisect.bisect_left(r,4)
    c3 = bisect.bisect_left(r,2)
    res = (25-c75) + (25-c25)*(25-(c3+1)) +(25 -c15)*(25-(c5+1)) + (25-c5)*(25-(c5+1))*(25-(c3+2))//2
    print(res)

Submission status: Accepted

Solution code:
from collections import Counter
import math
def P(n, r):
  return math.factorial(n)//math.factorial(n-r)
def C(n, r):
  return P(n, r)//math.factorial(r)
n=int(input())
L=[]
for j in range(2,n+1):
    I=j
    s=0
    R=int(I)
    while s==0:
        for i in range(2,R+1):
            if I%i==0:
                I=I/i
                if I==1:
                    s=1
                L.append(i)
                break
C=Counter(L)
c=[0 for i in range(100)]
for i,j in C.most_common():
  c[j]+=1
 
s=0
s+=sum(c[4:])*(sum(c[4:])-1)*(sum(c[2:])-2)//2
s+=sum(c[14:])*(sum(c[4:])-1)
s+=sum(c[24:])*(sum(c[2:])-1)
s+=sum(c[74:])
print(s)

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:
print(sorted([391,543]+[2,8,14,32,75,123,148,153,250,323,491]*2+[1,3,11,35,42,131,324,354]*4+[384]*5+[49,86,170,227,529]*6+[0]*10)[int(input())])