Problem p02541 (python)

Fixed submission:
import math

def gcd_ext(a, b):
    x, y, lastx, lasty = 0, 1, 1, 0
    while b != 0:
        q = a // b
        a, b = b, a % b
        x, y, lastx, lasty = lastx - q * x, lasty - q * y, x, y
    return (lastx, lasty)

n = int(input())
divisor_list = []
n *= 2
for x in range(2, int(n ** 0.5) + 1):
    if n % x == 0:
        divisor_list.append([x, n // x])
ans = n - 1
for m1, m2 in divisor_list:
    if math.gcd(m1, m2) != 1:
        continue
    p, q = gcd_ext(m1, m2)
    tmp = (-1 * m1 * p) % (m1 * m2)
    ans = min(tmp, ans)
    tmp = (-1 * m2 * q) % (m1 * m2)
    ans = min(tmp, ans)
print(ans)

Buggy submission (verdict: Runtime Error):
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

from collections import Counter
n = int(input())
prime_list = prime_factorize(n)
if n == 1:
    print(1)
    break

cnt = Counter(prime_list)
cnt_values = list(cnt.values())
value_list = [range(i + 1) for i in cnt_values]
iter_list = list(value_list[0])
iter_list = [[i] for i in iter_list]
for v_list in value_list[1:]:
    tmp = []
    for v in v_list:
        for i in iter_list:
            tmp.append(i + [v])
    iter_list = tmp
    
key_list = list(cnt.keys())
ans = n - 1
mod = 2 * n
for i_list in iter_list:
    tmp = 1
    for key, value in zip(key_list, i_list):
        tmp = tmp * pow(key, value)
    if tmp == 1:
        continue
    if tmp * (tmp - 1) % mod == 0:
        ans = min(ans, tmp - 1)
    if tmp * (tmp + 1) % mod == 0:
        ans = min(ans, tmp)
print(ans)

Buggy submission (verdict: Runtime Error):
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

from collections import Counter
n = int(input())
prime_list = prime_factorize(n)

cnt = Counter(prime_list)
cnt_values = list(cnt.values())
value_list = [range(i + 1) for i in cnt_values]
iter_list = list(value_list[0])
iter_list = [[i] for i in iter_list]
for v_list in value_list[1:]:
    tmp = []
    for v in v_list:
        for i in iter_list:
            tmp.append(i + [v])
    iter_list = tmp
    
key_list = list(cnt.keys())
ans = n - 1
mod = 2 * n
for i_list in iter_list:
    tmp = 1
    for key, value in zip(key_list, i_list):
        tmp = tmp * pow(key, value)
    if tmp == 1:
        continue
    if tmp * (tmp - 1) % mod == 0:
        ans = min(ans, tmp - 1)
    if tmp * (tmp + 1) % mod == 0:
        ans = min(ans, tmp)
print(ans)

Buggy submission (verdict: Runtime Error):
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

from collections import Counter
n = int(input())
prime_list = prime_factorize(n)

cnt = Counter(prime_list)
cnt_values = list(cnt.values())
value_list = [range(i + 1) for i in cnt_values]
iter_list = list(value_list[0])
iter_list = [[i] for i in iter_list]
for v_list in value_list[1:]:
    tmp = []
    for v in v_list:
        for i in iter_list:
            tmp.append(i + [v])
    iter_list = tmp
    
key_list = list(cnt.keys())
ans = n - 1
mod = 2 * n
for i_list in iter_list:
    tmp = 1
    for key, value in zip(key_list, i_list):
        tmp = tmp * pow(key, value)
    if tmp == 1:
        continue
    if tmp * (tmp - 1) % mod == 0:
        ans = min(ans, tmp - 1)
    if tmp * (tmp + 1) % mod == 0:
        ans = min(ans, tmp)
print(ans)