Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
from math import sqrt

def main():
    n = int(input())
    n_copy = n

    if n == 1:
        print(1)
        exit()

    if n % 2 == 0:
        ans = 2 * n - 1
        n *= 2
    else:
        ans = n - 1

    prime = [2, 3]
    for i in range(5, int(sqrt(n_copy)) + 1, 2):
        for p in prime:
            if p * p > i:
                prime.append(i)
                break

            if i % p == 0:
                break

    factors = []
    for p in prime:
        if p * p > n:
            if n > 1:
                factors.append(n)
            break

        if n % p == 0:
            cnt = 0
            while n % p == 0:
                cnt += 1
                n //= p
            factors.append(p ** cnt)

    for tf in product([True, False], repeat=len(factors)):
        a, b = 1, 1
        for i in range(len(factors)):
            if tf[i]:
                a *= factors[i]
            else:
                b *= factors[i]

        if a == 1 or b == 1:
            continue

        if a < b:
            a, b = b, a

        # Euclidean Algorithm
        # a*x - b*y = 1
        # quotient: 商
        l = []
        quo = []
        while a % b > 1:
            l.append(a)
            a = b
            quo.append(0)
            quo[-1], b = divmod(l[-1], b)
        x, y = 1, a//b
        flag = True
        while l:
            if flag:
                x += y * quo.pop()
                b = l.pop()
            else:
                y += x * quo.pop()
                a = l.pop()
            flag = not flag

        if ans > b * y:
            ans = b * y

    print(ans)

main()

Fixed submission:
from itertools import product

def main():
    n = int(input())
    n_copy = n

    if n == 1:
        print(1)
        exit()

    if n % 2 == 0:
        ans = 2 * n - 1
        n *= 2
    else:
        ans = n - 1

    factors = []
    for p in range(2, n):
        if p * p > n:
            if n > 1:
                factors.append(n)
            break

        if n % p == 0:
            cnt = 0
            while n % p == 0:
                cnt += 1
                n //= p
            factors.append(p ** cnt)

    for tf in product([True, False], repeat=len(factors)):
        a, b = 1, 1
        for i in range(len(factors)):
            if tf[i]:
                a *= factors[i]
            else:
                b *= factors[i]

        if a == 1 or b == 1:
            continue

        if a < b:
            a, b = b, a

        # Euclidean Algorithm
        # a*x - b*y = 1
        # quotient: 商
        l = []
        quo = []
        while a % b > 1:
            l.append(a)
            a = b
            quo.append(0)
            quo[-1], b = divmod(l[-1], b)
        x, y = 1, a//b
        flag = True
        while l:
            if flag:
                x += y * quo.pop()
                b = l.pop()
            else:
                y += x * quo.pop()
                a = l.pop()
            flag = not flag

        if ans > b * y:
            ans = b * y

    print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product

def main():
    n = int(input())

    if n == 1:
        print(1)
        exit()

    if n % 2 == 0:
        ans = 2 * n - 1
        n *= 2
    else:
        ans = n - 1

    prime = [2, 3]
    for i in range(5, 32 * (10**6), 2):
        for p in prime:
            if p * p > i:
                prime.append(i)
                break

            if i % p == 0:
                break

    factors = []
    for p in prime:
        if p * p > n:
            if n > 1:
                factors.append(n)
            break

        if n % p == 0:
            cnt = 0
            while n % p == 0:
                cnt += 1
                n //= p
            factors.append(p ** cnt)

    for tf in product([True, False], repeat=len(factors)):
        a, b = 1, 1
        for i in range(len(factors)):
            if tf[i]:
                a *= factors[i]
            else:
                b *= factors[i]

        if a == 1 or b == 1:
            continue

        if a < b:
            a, b = b, a

        # Euclidean Algorithm
        # a*x - b*y = 1
        # quotient: 商
        l = []
        quo = []
        while a % b > 1:
            l.append(a)
            a = b
            quo.append(0)
            quo[-1], b = divmod(l[-1], b)
        x, y = 1, a//b
        flag = True
        while l:
            if flag:
                x += y * quo.pop()
                b = l.pop()
            else:
                y += x * quo.pop()
                a = l.pop()
            flag = not flag

        if ans > b * y:
            ans = b * y

    print(ans)

main()

Fixed submission:
from itertools import product

def main():
    n = int(input())
    n_copy = n

    if n == 1:
        print(1)
        exit()

    if n % 2 == 0:
        ans = 2 * n - 1
        n *= 2
    else:
        ans = n - 1

    factors = []
    for p in range(2, n):
        if p * p > n:
            if n > 1:
                factors.append(n)
            break

        if n % p == 0:
            cnt = 0
            while n % p == 0:
                cnt += 1
                n //= p
            factors.append(p ** cnt)

    for tf in product([True, False], repeat=len(factors)):
        a, b = 1, 1
        for i in range(len(factors)):
            if tf[i]:
                a *= factors[i]
            else:
                b *= factors[i]

        if a == 1 or b == 1:
            continue

        if a < b:
            a, b = b, a

        # Euclidean Algorithm
        # a*x - b*y = 1
        # quotient: 商
        l = []
        quo = []
        while a % b > 1:
            l.append(a)
            a = b
            quo.append(0)
            quo[-1], b = divmod(l[-1], b)
        x, y = 1, a//b
        flag = True
        while l:
            if flag:
                x += y * quo.pop()
                b = l.pop()
            else:
                y += x * quo.pop()
                a = l.pop()
            flag = not flag

        if ans > b * y:
            ans = b * y

    print(ans)

main()