1

На входе - 4 числа n1, r1, n2, r2 (при этом n1 > 0, n2 > 0, 0 <=r1 < n1, 0 <= r2 < n2) Необходимо найти число r, такое, чтобы 0<= r < n1 * n2, r % n1 = r1, r % n2 = r2

Имеется рабочий код:

# определение наибольшего общего делителя - алгоритм Евклида

def gcd(a, b):
    assert a >= 0 and b >= 0 and a + b > 0

    while a > 0 and b > 0:
        if a >= b:
            a = a % b
        else:
            b = b % a
    return max(a, b)

# расширенный алгоритм Евклида
def extended_gcd(a, b):
    # assert c % gcd(a, b) == 0
    p = 1
    q = 0
    r = 0
    s = 1

    while a != 0 and b != 0:
        if a >= b:
            a = a - b
            p = p - r
            q = q - s
        else:
            b = b - a
            r = r - p
            s = s - q
    if a != 0:
        x = p
        y = q
    else:
        x = r
        y = s
    return x, y

def diophantine(a, b, c):
    # assert c % gcd(a, b) == 0
    # return (x, y) such that a * x + b * y = c
    (u, v) = extended_gcd(a, b)
    x = u * (c // gcd(a, b))
    y = v * (c // gcd(a, b))
    return x, y

def ChineseRemainderTheorem(n1, r1, n2, r2):
    (x, y) = diophantine(n1, n2, gcd(n1, n2))
    r = r1 * y * n2 + r2 * x * n1
    while r < 0:
        r += (n1 * n2)
    return r

Тест:

n1 = 686579304
r1 = 295310485
n2 = 26855093
r2 = 8217207
a = (ChineseRemainderTheorem(n1, r1, n2, r2))
print(a)
print(a % n1)
print(a % n2)

На выходе:

2988289728658869317843077
295310485
8217207

Проверяющая система не пропускает из-за того, что работает долго. Где можно соптимизироваться? (первые 3 функции убрать не получится - они зашиты в проверяющую систему)

2
  • 2
    и да, а вы уверены что ответ правильный? n1*n2 как бы меньше a. Замените while r < 0: r += (n1 * n2) на r %= n1 * n2
    – pavel
    2 сен 2018 в 19:01
  • 1
    @pavel и правда, какое-то неприлично большое число получилось))) Теперь все правильно, спасибо!
    – Lazarevna
    2 сен 2018 в 19:31

1 ответ 1

1

Пайтон не оптимизирующий интерпретатор. Он делает то что вы его просите. Поэтому в 2 раза быстрее будет например если

x = u * (c // gcd(a, b))
y = v * (c // gcd(a, b))

заменить на:

_ = c // gcd(a, b)
x = u * _
y = v * _

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.