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: Wrong Answer

Solution code:
import math
n = int(input())
lis = [0] * n
for i in range(2,n+1):
    now = i
    for j in range(2,math.ceil(math.sqrt(i))+1):
        while now % j == 0:
            now //= j
            lis[j-1] += 1
    if now != 1:
        lis[now-1] += 1

  # print(lis)

ans = 0

two = 0
four = 0
fourteen = 0
twentyfour = 0
seventyfour = 0
for num in lis:
    if num >= 74:
        seventyfour += 1
    if num >= 24:
        twentyfour += 1
    if num >= 14:
        fourteen += 1
    if num >= 4:
        four += 1
    if num >= 2:
        two += 1

ans += seventyfour

if twentyfour >= 2:
    ans += (twentyfour * (twentyfour - 1))//2

if twentyfour:
    ans += twentyfour * (two -twentyfour)

if fourteen:
    ans += fourteen * (four -fourteen)

if two and four >= 2:
    ans += two * ((four-two) * (four - two - 1)) // 2

if four >= 3:
    ans += (four * (four - 1) * (four - 2)) // 3

print(ans)

Submission status: Wrong Answer

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

import sys
import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    class Eratos:
        def __init__(self, num):
            '''
            O(nlglgn) で num までの素数判定テーブルを作る
            >>> e = Eratos(10)
            >>> e.table
            [False, False, True, True, False, True, False, True, False, False, False]
            '''
            assert(num >= 1)
            self.table_max = num
            # self.table[i] は i が素数かどうかを示す (bool)
            self.table = [False if i == 0 or i == 1 else True for i in range(num+1)]
            for i in range(2, int(math.sqrt(num)) + 1):
                if self.table[i]:
                    for j in range(i ** 2, num + 1, i):    # i**2 からスタートすることで定数倍高速化できる
                        self.table[j] = False
        
        def is_prime(self, num):
            '''
            O(1) で素数判定を行う
            >>> e = Eratos(100)
            >>> [i for i in range(1, 101) if e.is_prime(i)]
            [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]
            '''
            assert(num >= 1)
            if num > self.table_max:
                raise ValueError('Eratos.is_prime(): exceed table_max({}). got {}'.format(self.table_max, num))
            return self.table[num]
        
        def prime_factorize(self, num):
            '''
            O(√n) で素因数分解を行う
            >>> e = Eratos(10000)
            >>> e.prime_factorize(6552)
            {2: 3, 3: 2, 7: 1, 13: 1}
            '''
            assert(num >= 1)
            if int(math.sqrt(num)) > self.table_max:
                raise ValueError('Eratos.prime_factorize(): exceed prime table size. got {}'.format(num))
            # 素因数分解の結果を記録する辞書        
            factorized_dict = dict()
            candidate_prime_numbers = [i for i in range(2, int(math.sqrt(num)) + 1) if self.is_prime(i)]
            # n について、√n 以下の素数で割り続けると最後には 1 or 素数となる
            # 背理法を考えれば自明 (残された数が √n より上の素数の積であると仮定。これは自明に n を超えるため矛盾)
            for p in candidate_prime_numbers:
                if num == 1:    # これ以上調査は無意味
                    break
                if num % p == 0:
                    cnt = 0
                    while num % p == 0:
                        num //= p
                        cnt += 1
                    factorized_dict[p] = cnt
            if num != 1:
                factorized_dict[num] = 1
            return factorized_dict
        
        def enum_divisor(self, num):
            '''
            O(√n) で約数列挙を行う
            >>> e = Eratos(10000)
            >>> e.enum_divisor(4)
            [1, 2, 4]
            >>> e.enum_divisor(19)
            [1, 19]
            >>> e.enum_divisor(100)
            [1, 2, 4, 5, 10, 20, 25, 50, 100]
            '''
            divisor_small = []
            divisor_large = []
            for i in range(1, int(math.sqrt(num)) + 1):
                if num % i == 0:
                    divisor_small.append(i)
                    if i != num // i:
                        divisor_large.append(num // i)
            divisor_large.reverse()
            return divisor_small + divisor_large
    
    n = ii()
    e = Eratos(n)
    c = Counter()
    for i in range(2, n + 1):
        c += Counter(e.prime_factorize(i))
    # print(c)
    
    gt_74_candidate = 0
    gt_24_candidate = 0
    gt_14_candidate = 0
    gt_4_candidate = 0
    gt_2_candidate = 0
    for _, v in c.items():
        if v >= 2:
            gt_2_candidate += 1
        if v >= 4:
            gt_4_candidate += 1
        if v >= 14:
            gt_14_candidate += 1
        if v >= 24:
            gt_24_candidate += 1
        if v >= 74:
            gt_74_candidate += 1
    
    def calc_3_5_5(a, b):
        res = a - b
        if a >= 3 and b >= 2:
            # bC2 * resC1 + bC3
            return (b * (b-1) // 2) * res + (b * (b-1) * (b-2) // 6)
        else:
            return 0
    
    def calc_5_15(a, b):
        res = a - b
        if a >= 2 and b >= 1:
            # bC1 * resC1 + bC2
            return b * res + (b * (b-1) // 2) 
        else:
            return 0
    
    def calc_3_25(a, b):
        res = a - b
        if a >= 2 and b >= 1:
            # bC1 * resC1 + bC2
            return b * res + (b * (b-1) // 2)
        else:
            return 0
    
    def calc_75(a):
        if a >= 1:
            return a
        else:
            return 0


    def calc_all_75_num(gt_2_candidate, gt_4_candidate, gt_14_candidate, gt_24_candidate, gt_74_candidate):
        ans = 0
        ans += calc_3_5_5(gt_2_candidate, gt_4_candidate)
        # print(ans)
        ans += calc_5_15(gt_4_candidate, gt_14_candidate)
        # print(ans)
        ans += calc_3_25(gt_2_candidate, gt_24_candidate)
        # print(ans)
        ans += calc_75(gt_74_candidate)
        # print(ans)
        return ans
    
    print(calc_all_75_num(gt_2_candidate, gt_4_candidate, gt_14_candidate, gt_24_candidate, gt_74_candidate))



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

import sys
import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    class Eratos:
        def __init__(self, num):
            '''
            O(nlglgn) で num までの素数判定テーブルを作る
            >>> e = Eratos(10)
            >>> e.table
            [False, False, True, True, False, True, False, True, False, False, False]
            '''
            assert(num >= 1)
            self.table_max = num
            # self.table[i] は i が素数かどうかを示す (bool)
            self.table = [False if i == 0 or i == 1 else True for i in range(num+1)]
            for i in range(2, int(math.sqrt(num)) + 1):
                if self.table[i]:
                    for j in range(i ** 2, num + 1, i):    # i**2 からスタートすることで定数倍高速化できる
                        self.table[j] = False
        
        def is_prime(self, num):
            '''
            O(1) で素数判定を行う
            >>> e = Eratos(100)
            >>> [i for i in range(1, 101) if e.is_prime(i)]
            [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]
            '''
            assert(num >= 1)
            if num > self.table_max:
                raise ValueError('Eratos.is_prime(): exceed table_max({}). got {}'.format(self.table_max, num))
            return self.table[num]
        
        def prime_factorize(self, num):
            '''
            O(√n) で素因数分解を行う
            >>> e = Eratos(10000)
            >>> e.prime_factorize(6552)
            {2: 3, 3: 2, 7: 1, 13: 1}
            '''
            assert(num >= 1)
            if int(math.sqrt(num)) > self.table_max:
                raise ValueError('Eratos.prime_factorize(): exceed prime table size. got {}'.format(num))
            # 素因数分解の結果を記録する辞書        
            factorized_dict = dict()
            candidate_prime_numbers = [i for i in range(2, int(math.sqrt(num)) + 1) if self.is_prime(i)]
            # n について、√n 以下の素数で割り続けると最後には 1 or 素数となる
            # 背理法を考えれば自明 (残された数が √n より上の素数の積であると仮定。これは自明に n を超えるため矛盾)
            for p in candidate_prime_numbers:
                if num == 1:    # これ以上調査は無意味
                    break
                if num % p == 0:
                    cnt = 0
                    while num % p == 0:
                        num //= p
                        cnt += 1
                    factorized_dict[p] = cnt
            if num != 1:
                factorized_dict[num] = 1
            return factorized_dict
        
        def enum_divisor(self, num):
            '''
            O(√n) で約数列挙を行う
            >>> e = Eratos(10000)
            >>> e.enum_divisor(4)
            [1, 2, 4]
            >>> e.enum_divisor(19)
            [1, 19]
            >>> e.enum_divisor(100)
            [1, 2, 4, 5, 10, 20, 25, 50, 100]
            '''
            divisor_small = []
            divisor_large = []
            for i in range(1, int(math.sqrt(num)) + 1):
                if num % i == 0:
                    divisor_small.append(i)
                    if i != num // i:
                        divisor_large.append(num // i)
            divisor_large.reverse()
            return divisor_small + divisor_large
    
    n = ii()
    e = Eratos(n)
    c = Counter()
    for i in range(2, n + 1):
        c += Counter(e.prime_factorize(i))
    print(c)
    
    gt_74_candidate = 0
    gt_24_candidate = 0
    gt_14_candidate = 0
    gt_4_candidate = 0
    gt_2_candidate = 0
    for _, v in c.items():
        if v >= 2:
            gt_2_candidate += 1
        if v >= 4:
            gt_4_candidate += 1
        if v >= 14:
            gt_14_candidate += 1
        if v >= 24:
            gt_24_candidate += 1
        if v >= 74:
            gt_74_candidate += 1
    
    def calc_3_5_5(a, b):
        res = a - b
        if a >= 3 and b >= 2:
            # bC2 * resC1 + bC3
            return (b * (b-1) // 2) * res + (b * (b-1) * (b-2) // 6)
        else:
            return 0
    
    def calc_5_15(a, b):
        res = a - b
        if a >= 2 and b >= 1:
            # bC1 * resC1 + bC2
            return b * res + (b * (b-1) // 2) 
        else:
            return 0
    
    def calc_3_25(a, b):
        res = a - b
        if a >= 2 and b >= 1:
            # bC1 * resC1 + bC2
            return b * res + (b * (b-1) // 2)
        else:
            return 0
    
    def calc_75(a):
        if a >= 1:
            return a
        else:
            return 0


    def calc_all_75_num(gt_2_candidate, gt_4_candidate, gt_14_candidate, gt_24_candidate, gt_74_candidate):
        ans = 0
        ans += calc_3_5_5(gt_2_candidate, gt_4_candidate)
        print(ans)
        ans += calc_5_15(gt_4_candidate, gt_14_candidate)
        print(ans)
        ans += calc_3_25(gt_2_candidate, gt_24_candidate)
        print(ans)
        ans += calc_75(gt_74_candidate)
        # print(ans)
        return ans
    
    print(calc_all_75_num(gt_2_candidate, gt_4_candidate, gt_14_candidate, gt_24_candidate, gt_74_candidate))



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from functools import reduce
import collections

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

n = int(input())

cnt_75 = 0
for d in range(1, n+1):
    combs = combinations(range(2, n+1), d)
    for comb in combs: 
        yakusu = reduce(lambda x, y: x*y, comb)

        c = collections.Counter(prime_factorize(yakusu))
        pow_cnt = [x+1 for x in c.values()]
        num_of_pow = reduce(lambda x, y: x*y, pow_cnt)
        if num_of_pow == 75:
            cnt_75 += 1
print(cnt_75)

Submission status: Wrong Answer

Solution code:
import sys


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


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


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

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

    return d


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

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

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

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

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

n = int(input())

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

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

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


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


print(b + c + d + e)

Submission status: Wrong Answer

Solution code:
n = int(input())
dic = {}
for i in range(2, n+1):
    num = i
    for j in range(2, num+1):
        c = 0
        while num%j==0:
            c += 1
            num //= j
        if c > 0:
            if j in dic:
                dic[j] += c
            else:
                dic[j] = c
t, f, ft, tw = 0,0,0,0
end = 0
for _i, j in dic.items():
    if j >= 2:
        t += 1
        if j >= 4:
            f += 1
            if j >= 14:
                ft += 1
                if j >= 24:
                    tw += 1
                    if j >= 74:
                        end += 1

result = 0

result += (t-f)*f*(f-1)//2
if f > 2:
    result += f*(f-1)*(f-2)//6
result += (t-tw)*tw
if tw > 1:
    result += tw*(tw-1)//2
result += (f-ft)*ft
if ft > 1:
    result += ft*(ft-1)//2
result += end
print(result)

Submission status: Wrong Answer

Solution code:
from functools import reduce

def comb(n, r):
    if n < 0 or r < 0 or r > n:
        return 0
    r = min(r, n - r)
    if r == 0: return 1

    numer = [n - r + i + 1 for i in range(r)]
    denom = [i + 1 for i in range(r)]

    for i in range(1, r):
        divisor = denom[i]
        if divisor > 1:
            offset = (n - r) % (i + 1)
            for j in range(i, r, i+1):
                numer[j - offset] //= divisor
                denom[j] //= divisor

    return reduce(lambda x, y: x*y if y > 1 else x, numer)

def sieve(n):
    a = [1] * (n + 1)
    a[0] = a[1] = False
    for i in range(4, n+1, 2):
        a[i] = False
    lim = int(n**0.5) + 1
    for i in range(3, lim + 1, 2):
        if a[i]:
            for j in range(i + i, n + 1, i):
                a[j] = False
    return a

N = int(input())

factors = []
sv = sieve(N)
for p in range(2, N+1):
    if sv[p]:
        n = N
        x = 0
        while n // p > 0:
            n //= p
            x += n
        if x > 0:
            factors.append([p, x])

# print(factors)
ans = 0
for xx in [[[4,2],[2,1]],[[14,1],[4,1]],[[24,1],[2,1]],[[75,1]]]:
    c = 1
    done = 0
    for i, x in enumerate(xx):
        s = sum(f[1] >= x[0] for f in factors)
        s = max(0, s - done)
        if s < x[1]:
            c = 0
            break
        else:
            c *= comb(s, x[1])
            done += x[1]
    ans += c

print(ans)

Submission status: Wrong Answer

Solution code:
# なぜかうまくいかない
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_right, bisect_left

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

e = [0] * (N + 1)

for i in range(2, N + 1):
    cur = i
    for j in range(2, N + 1):
        while cur % j == 0:
            # 割り切れるなら，割り切れるjの数を数える
            e[j] += 1
            cur //= j
def num(m):
    return len(list(filter (lambda x: x > m - 1, e)))

ans = num(75) + num(25) * (num(3) - 1) + num(15) * (num(5) - 1) + num(5) * (num(5) - 1) * (num(3) - 2) // 2
print(ans)
# for n in range(1, N+1):
#     prime = prime_decomposition(n)
#     print(prime)
#     for p in prime:
#         p = int(p)
#         prime_num[p] += 1
# print(prime_num)
# num = [0] * 81
# for p_num in prime_num:
#     # if p_num <= 80:
#     p_num = min(80, p_num)
#     for i in range(1, p_num+1):
#         num[i] += 1
# print(num)
# # 同じ素数は取らないように
# 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: Wrong Answer

Solution code:
from collections import Counter

def fctr1(n): 
    f = []
    for i in range(2,int(n**0.5)+2):
        while n%i == 0:
            n = n//i
            f.append(i)
    if n != 1:
        f.append(n)
    return f

n = int(input())

p_list = []
for i in range(1,n+1):
    p_list = p_list + fctr1(i)

pc = Counter(p_list).most_common()

#print(pc)

c75 = 0
c24 = 0
c14 = 0
c4 = 0
c2 = 0

for i in range(len(pc)):
    if pc[i][1] >= 75:
        c75 += 1
    if pc[i][1] >= 24:
        c24 += 1
    if pc[i][1] >= 14:
        c14 += 1
    if pc[i][1] >= 4:
        c4 += 1
    if pc[i][1] >= 2:
        c2 += 1

ans = c75 + c24*(c2-1) + c14*(c4-1) + c4*(c4-1)//2*(c2-2)

print(ans)

Submission status: Wrong Answer

Solution code:
x=[]

for j in range(100):
    m=j+1
    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
    x.append(pf)

N=int(input())
if N==1:
    print(0)
    exit()

from collections import defaultdict
d=defaultdict(int)
for i in range(1,N):
    for k in x[i].keys():
        d[k]+=x[i][k]

print(d)
over2=0
over4=0
over14=0
over24=0
over74=0
for k in d.keys():
    if d[k]>=2:
        over2+=1
    if d[k]>=4:
        over4+=1
    if d[k]>=14:
        over14+=1
    if d[k]>=24:
        over24+=1
    if d[k]>=74:
        over74+=1

ans=0
#case1
ans+=over4*(over4-1)//2*(over2-2)
#case2
ans+=over14*(over4-1)
#case3
ans+=over24*(over2-1)
#case4
ans+=over74
print(ans)

Submission status: Wrong Answer

Solution code:
def sieve(n):
    prime=[]
    limit=n**0.5
    data=[i+1 for i in range(1,n)]
    while True:
        p=data[0]
        if limit<=p:
            return prime+data
        prime.append(p)
        data=[e for e in data if e%p!=0]

def main():
    n=int(input())
    primes=sieve(n+1)
    l=len(primes)

    factor=[]
    for i in range(l):
        p = primes[i]
        cnt = 0
        while p <= n:
            cnt += n//p
            p *= p
        factor.append(cnt)
    
    l2=len(factor)
    idx=[0,0,0,0,0]
    fac=[2,4,14,24,74]
    j,i=4,0
    while i<l2:
        if  factor[i] < fac[j]:
            idx[j] = i
            j-=1
            if j==-1:
                break
        else:
            i+=1

    ans=idx[4]+idx[3]*max(0,idx[0]-1)+idx[2]*max(0,idx[1]-1)+idx[1]*max(0,idx[1]-1)*max(0,idx[0]-2)//2
    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
#114_D
prime=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
N=int(input())

def Count(x):
    res=0
    tmp=N
    while tmp//x:
        tmp=tmp//x
        res+=tmp
    return res

cnt_2=sum([Count(p)>=2 for p in prime])
cnt_4=sum([Count(p)>=4 for p in prime])

print(cnt_4*(cnt_4-1)*(cnt_2-2)//2)

Submission status: Wrong Answer

Solution code:
def wareru(n,k):
    res = 0
    for i in range(1,n):
        plus = n//(k**i)
        res+= plus
        if plus == 0:break
    return res
n = int(input())
prime = [2,3,5,7,11,13,17,19,23,27,29,31,37,41,43,47]
a = []
for p in prime :
    if wareru(n,p) > 1:
        a.append(wareru(n,p))
    else:break
cnt = [0]*5
for num in a:
    if num >= 74:
        cnt[0]+=1
    if num >= 24:
        cnt[1] +=1
    if num >= 14:
        cnt[2] += 1
    if num >= 4:
        cnt[3] += 1
    cnt[4]+= 1
ans = cnt[0]
ans += cnt[1]*(cnt[4]-1)
ans += cnt[2]*(cnt[3]-1)
ans += cnt[3]*(cnt[3]-1)*(cnt[4]-2)
print(ans//2)

Submission status: Wrong Answer

Solution code:
def wareru(n,k):
    res = 0
    for i in range(1,n):
        plus = n//(k**i)
        res+= plus
        if plus == 0:break
    return res
n = int(input())
prime = [2,3,5,7,11,13,17,19,23,27,29,31,37,41,43,47]
a = []
for p in prime :
    if wareru(n,p) > 1:
        a.append(wareru(n,p))
    else:break
cnt = [0]*5
for num in a:
    if num >= 74:
        cnt[0]+=1
    if num >= 24:
        cnt[1] +=1
    if num >= 14:
        cnt[2] += 1
    if num >= 4:
        cnt[3] += 1
    cnt[4]+= 1
ans = cnt[0]
ans += cnt[1]*(cnt[4]-1)
ans += cnt[2]*(cnt[3]-1)
ans += cnt[3]*(cnt[3]-1)*(cnt[4]-2)
print(cnt)
print(ans//2)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc114/tasks/abc114_d

# 75数...約数をちょうど75個持つ整数
# 約数がちょうど75個→ その数を素因数分解すると
# A**74 or A**2 * B**4 * C**4 or A**2 * B**24 or A**16 * B**4 (必要条件？)

# N！の約数である→N!を割り切れる→素因数分解の肩の数が大きい

# N!の素因数分解の結果に対して、指数が4以上→2つ必要、2以上→1つ必要
# 一般化する。指数が4以上である底の個数をB,指数が2以上4未満である底の個数をAと定義した場合
# BC2 * A + BC3 が答えとなる


def factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 1):  # ここにバグがないか心配
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append((i, cnt))

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

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

    return arr


def make_divisors(n: int, sort=False):
    # 約数列挙
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    if sort:
        divisors.sort()
    return divisors


def combination_mod(n, r, mod):
    if r > n:
        return 0  # このような通りの数は無いため便宜上こう定義する
    r = min(r, n - r)
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
    return nf * pow(rf, mod - 2, mod) % mod


from collections import defaultdict

N = int(input())
fact = defaultdict(lambda: 0)
for n in range(1, N + 1):
    tmp = factorization(n)
    for k, v in tmp:
        fact[k] += v

# A**74 or B**2 * C**4 * D**4 or E**2 * F**24 or G**16 * H**4 (必要条件？)
A, B, C, D, E, F, G, H = 0, 0, 0, 0, 0, 0, 0, 0
for k, v in fact.items():
    if v >= 74:
        A += 1

    if v >= 4:
        C += 1
    if 2 <= v < 4:
        B += 1

    if v >= 24:
        F += 1
    if 24 > v >= 2:
        E += 1

    if v >= 16:
        G += 1
    if 16 > v >= 4:
        H += 1


# print(fact)
MOD = 10**9 + 7
ans = A
ans += combination_mod(C, 2, MOD) * B + combination_mod(C, 3, MOD) * 3
ans += E * F + combination_mod(F, 2, MOD) * 2
ans += G * H + combination_mod(G, 2, MOD) * 2

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n=int(input())
sosu_list=[2]
for i in range(3, 101, 2):
    flag=0
    for j in range(2, int(i**0.5)+2):
        if i%j==0:
            flag=1
    if flag==0:
        sosu_list.append(i)
print(sosu_list)
soinsu=defaultdict(int)
for i in sosu_list:
    temp=n
    while temp>=i:
        temp//=i
        soinsu[i]+=temp
kouho=soinsu.values()
cnt3=0
cnt5=0
cnt15=0
cnt25=0
cnt75=0
for a in kouho:
    if a>=2:
        cnt3+=1
    if a>=4:
        cnt5+=1
    if a>=14:
        cnt15+=1
    if a>=24:
        cnt25+=1
    if a>=74:
        cnt75+=1
ans=0
ans+=cnt75
ans+=cnt15*(cnt5-1)
ans+=cnt25*(cnt3-1)
if cnt3>=2:
    ans+=cnt5*(cnt5-1)*(cnt3-2)//2
        
print(ans)