Problem p03213 (python)

Fixed submission:
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    N = int(input())
    h = list(map(int, input().split()))

    import math

    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f

    def make_prime_list_2(num):
        if num < 2:
            return []

        # 0のものは素数じゃないとする
        prime_list = [i for i in range(num + 1)]
        prime_list[1] = 0  # 1は素数ではない
        num_sqrt = math.sqrt(num)

        for prime in prime_list:
            if prime == 0:
                continue
            if prime > num_sqrt:
                break

            for non_prime in range(2 * prime, num, prime):
                prime_list[non_prime] = 0

        return [prime for prime in prime_list if prime != 0]

    def prime_factorization_2(num, dict_counter):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""

        if num <= 1:
            # 例えば1を食ったときの対処の仕方は問題によって違うと思うのでそのつど考える。
            # cf. https://atcoder.jp/contests/abc110/submissions/12688244
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)

            # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452

            for prime in prime_list:
                while num % prime == 0:
                    if prime in dict_counter:
                        dict_counter[prime] += 1
                    else:
                        dict_counter[prime] = 1
                    num //= prime
            if num != 1:
                if num in dict_counter:
                    dict_counter[num] += 1
                else:
                    dict_counter[num] = 1

            return dict_counter
    dict_counter = {}
    for i in range(1, N+1):
        prime_factorization_2(i, dict_counter)

    l = list(dict_counter.values())
    ll = len(l)
    
    cnts={2:0,4:0,14:0,24:0,74:0}

    cnt=0
    for i in l:
        if i>=2:
            cnts[2]+=1
        if i>=4:
            cnts[4]+=1
        if i>=14:
            cnts[14]+=1
        if i>=24:
            cnts[24]+=1
        if i>=74:
            cnts[74]+=1
    ans=0
    ans+=cnts[4]*(cnts[4]-1)//2*(cnts[2]-2)
    ans+=cnts[14]*(cnts[4]-1)+cnts[24]*(cnts[2]-1)
    ans+=cnts[74]
    print(ans)
                


    


resolve()

Buggy submission (verdict: Runtime Error):
# import bisect
# from collections import Counter, deque # https://note.nkmk.me/python-scipy-connected-components/
# from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    N = int(input())
    h = list(map(int, input().split()))

    import math

    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f

    def make_prime_list_2(num):
        if num < 2:
            return []

        # 0のものは素数じゃないとする
        prime_list = [i for i in range(num + 1)]
        prime_list[1] = 0  # 1は素数ではない
        num_sqrt = math.sqrt(num)

        for prime in prime_list:
            if prime == 0:
                continue
            if prime > num_sqrt:
                break

            for non_prime in range(2 * prime, num, prime):
                prime_list[non_prime] = 0

        return [prime for prime in prime_list if prime != 0]

    def prime_factorization_2(num, dict_counter):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""

        if num <= 1:
            # 例えば1を食ったときの対処の仕方は問題によって違うと思うのでそのつど考える。
            # cf. https://atcoder.jp/contests/abc110/submissions/12688244
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)

            # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452

            for prime in prime_list:
                while num % prime == 0:
                    if prime in dict_counter:
                        dict_counter[prime] += 1
                    else:
                        dict_counter[prime] = 1
                    num //= prime
            if num != 1:
                if num in dict_counter:
                    dict_counter[num] += 1
                else:
                    dict_counter[num] = 1

            return dict_counter
    dict_counter = {}
    for i in range(1, N+1):
        prime_factorization_2(i, dict_counter)

    l = list(dict_counter.values())
    ll = len(l)

    cnt=0
    for i in range(ll-2):
        for j in range(i+1,ll-1):
            for k in range(j+1,ll):
                if (l[i]>=4 and l[j]>=4 and l[k]>=2) or (l[i]>=4 and l[j]>=2 and l[k]>=4) or (l[i]>=2 and l[j]>=4 and l[k]>=4):
                    cnt+=1
    
    for i in range(ll-1):
        for j in range(i+1,ll):
            if (l[i]>=4 and l[j]>=14) or (l[i]>=14 and l[j]>=4):
                cnt+=1
            if (l[i]>=24 and l[j]>=2) or (l[i]>=2 and l[j]>=24):
                cnt+=1
    
    for i in range(ll):
        if l[i]>=54:
            cnt+=1
    print(cnt)
                


    


# resolve()


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """9"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """10"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """100"""
        output = """543"""
        self.assertIO(input, output)


if __name__ == "__main__":
    unittest.main()

Buggy submission (verdict: Runtime Error):
# import bisect
# from collections import Counter, deque # https://note.nkmk.me/python-scipy-connected-components/
# from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    N = int(input())
    h = list(map(int, input().split()))

    import math

    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f

    def make_prime_list_2(num):
        if num < 2:
            return []

        # 0のものは素数じゃないとする
        prime_list = [i for i in range(num + 1)]
        prime_list[1] = 0  # 1は素数ではない
        num_sqrt = math.sqrt(num)

        for prime in prime_list:
            if prime == 0:
                continue
            if prime > num_sqrt:
                break

            for non_prime in range(2 * prime, num, prime):
                prime_list[non_prime] = 0

        return [prime for prime in prime_list if prime != 0]

    def prime_factorization_2(num, dict_counter):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""

        if num <= 1:
            # 例えば1を食ったときの対処の仕方は問題によって違うと思うのでそのつど考える。
            # cf. https://atcoder.jp/contests/abc110/submissions/12688244
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)

            # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452

            for prime in prime_list:
                while num % prime == 0:
                    if prime in dict_counter:
                        dict_counter[prime] += 1
                    else:
                        dict_counter[prime] = 1
                    num //= prime
            if num != 1:
                if num in dict_counter:
                    dict_counter[num] += 1
                else:
                    dict_counter[num] = 1

            return dict_counter
    dict_counter = {}
    for i in range(1, N+1):
        prime_factorization_2(i, dict_counter)

    l = list(dict_counter.values())
    ll = len(l)

    num, sum = [0] * (ll+1), [0] * 76

    # dp[i][j]:i-1番目までの素因数を使うと約数の個数がj個になる数が何個あるか
    dp = [[0] * 76 for _ in range(ll + 1)]
    dp[0][1] = 1

    for i in range(ll):
        for j in range(200):# dp[i][j]はdp[i+1][...]にどう寄与するか？
            dp[i+1][j*(l[i]+1)] += dp[i][j]

    print(dp[ll][75])


# resolve()


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """9"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """10"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """100"""
        output = """543"""
        self.assertIO(input, output)


if __name__ == "__main__":
    unittest.main()