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 that you have read and understand our privacy policy and code of conduct.

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