Problem p03253 (python)

Fixed submission:
import math

# import time


def get_primes(n):
    primes = []
    checks = [True for _ in range(int(math.sqrt(n)) + 1)]
    checks[0] = checks[1] = False
    for i in range(2, len(checks)):
        if checks[i]:
            primes.append(i)
            tmp = 0
            while i + tmp * i < len(checks):
                checks[i + tmp * i] = False
                tmp += 1
    return primes


def combination(a, b):
    i = 1
    for _i in range(a - b + 1, a + 1):
        i *= _i
    return i // math.factorial(b)


n, m = map(int, input().split())
# start = time.time()
primes = get_primes(m)
elems = []
m_copy = m
divides = dict()
for _p in primes:
    while m_copy % _p == 0:
        m_copy = m_copy // _p
        if str(_p) in divides.keys():
            divides[str(_p)] += 1
        else:
            divides[str(_p)] = 1
if m_copy > 1:
    divides[str(m_copy)] = 1
# print(primes)

# print(time.time() - start)
ans = 1
for i in divides.values():
    ans *= combination(i + n - 1, i)
print(ans % (1000000007))
# print(time.time() - start)

Buggy submission (verdict: Runtime Error):
from collections import Counter
from operator import mul
from functools import reduce
from math import factorial


def solve(s):
    n, m = map(int, s.split())
    divisor = []
    for i in range(2, int(m**0.5) + 1):
        if m % i == 0:
            divisor.append(i)
    divisor += [m // d for d in divisor[::-1]] + [m]
    ld = len(divisor)

    def search(ded, use, j):
        if ded == 0:
            return 0
        if ded == 1:
            count = Counter(use)
            base = reduce(mul, range(n - len(use) + 1, n + 1))
            for v in list(count.values()):
                base //= factorial(v)
            return base
        if len(use) >= n:
            return 0

        tmp = [
            search(ded // divisor[i], use + [divisor[i]], i)
            for i in range(j, ld)
            if ded % divisor[i] == 0
        ]
        return sum(tmp) if tmp else 0

    return search(m, [], 0) % (10**9 + 7)


print(solve(input()))

Buggy submission (verdict: Runtime Error):
from collections import Counter
from operator import mul
from functools import reduce
from math import factorial


def solve(s):
    n, m = map(int, s.split())
    divisor = []
    for i in range(2, int(m**0.5) + 1):
        if m % i == 0:
            divisor.append(i)
    divisor += [m // d for d in divisor[::-1]] + [m]
    ld = len(divisor)

    def search(ded, use, j):
        if ded == 0:
            return 0
        if ded == 1:
            count = Counter(use)
            base = reduce(mul, range(n - len(use) + 1, n + 1))
            for v in list(count.values()):
                base //= factorial(v)
            return base
        if len(use) >= n:
            return 0

        tmp = [
            search(ded // divisor[i], use + [divisor[i]], i)
            for i in range(j, ld)
            if ded % divisor[i] == 0
        ]
        return sum(tmp) if tmp else 0

    return search(m, [], 0) % (10**9 + 7)


print(solve(input()))

Buggy submission (verdict: Runtime Error):
import math
# import time


def get_primes(n):
    primes = []
    checks = [True for _ in range(int(math.sqrt(n)))]
    checks[0] = checks[1] = False
    for i in range(2, len(checks)):
        if checks[i]:
            primes.append(i)
            tmp = 0
            while i + tmp * i < len(checks):
                checks[i + tmp * i] = False
                tmp += 1
    return primes


def combination(a, b):
    i = 1
    for _i in range(a - b+1, a + 1):
        i *= _i
    return i // math.factorial(b)


n, m = map(int, input().split())
# start = time.time()
primes = get_primes(m)
elems = []
m_copy = m
divides = dict()
for _p in primes:
    while m_copy % _p == 0:
        m_copy = m_copy // _p
        if str(_p) in divides.keys():
            divides[str(_p)] += 1
        else:
            divides[str(_p)] = 1
if m_copy > 1:
    divides[str(m_copy)] = 1

# print(time.time() - start)
ans = 1
for i in divides.values():
    ans *= combination(i + n - 1, i)
print(ans % (1000000007))
# print(time.time() - start)

Buggy submission (verdict: Runtime Error):
import math


# """
def get_primes(n):
    primes = []
    checks = [True for _ in range(int(math.sqrt(n)))]
    checks[0] = checks[1] = False
    for i in range(2, len(checks)):
        if checks[i]:
            primes.append(i)
            tmp = 0
            while i + tmp * i < len(checks):
                checks[i + tmp * i] = False
                tmp += 1
    return primes


def combination(a, b):
    return math.factorial(a) // math.factorial(a - b) // math.factorial(b)


n, m = map(int, input().split())
primes = get_primes(m)
elems = []
m_copy = m
divides = dict()
for _p in primes:
    while m_copy % _p == 0:
        m_copy = m_copy // _p
        if str(_p) in divides.keys():
            divides[str(_p)] += 1
        else:
            divides[str(_p)] = 1
if m_copy > 1:
    divides[str(m_copy)] = 1
ans = 1
for i in divides.values():
    ans *= combination(i + n - 1, i)
print(ans % (1000000007))