Найти число B такое что A*B+A+B делится на N для заданных A и N

#python #алгоритм #python_3x

f = open("input.txt", "r")
z = open("output.txt", "w+")
F = f.read()
A, N = map(int, F.split())
B = 0
с = 0
for B in range(10**9):
    if (A * B + A + B) % N == 0:
        с = 1
        break
if c != 1:
    B = -1
z.write(str(B))
f.close()
z.close()


Даются два числа. A и N. Надо найти такое B, чтобы (AB+A+B)%N=0 (сумма произведения
и суммы делится на N).
Ограничение по времени - одна секунда.
Перебор подходит только для малых чисел.
Если такого числа B нет, то выводим -1.

Как быстро проверить все числа B (B не больше 10**9)?
    

Ответы

Ответ 1

Можно решить быстро без перебора, просто за счёт нахождения обратного по модулю N числа. 

Вначале переписываем выражение 

A * B + A + B = 0 (mod N) 
         ⇓
(A + 1) * (B + 1) = 1 (mod N) 
         ⇓ 
B = (A + 1)^(-1) - 1 (mod N)


Потом используем для инверсии A + 1 Расширенный Эвклидов Алгоритм, алгоритм работает
почти мгновенно и не требует перебора. 

Вот полный код на Питоне (Запустить онлайн):

def inverse(a, n):
    (t, newt, r, newr) = (0, 1, n, a)
    while newr != 0:
        quotient = r // newr
        (t, newt) = (newt, t - quotient * newt) 
        (r, newr) = (newr, r - quotient * newr)
    if r > 1:
        raise ValueError("a is not invertible")
    if t < 0:
        t = t + n
    return t

def main():
    # A * B + A + B = 0 (mod N) <=> (A + 1) * (B + 1) = 1 (mod N) <=> B = (A + 1)^(-1)
- 1 (mod N)
    A = 10
    N = 997
    B = 0

    try:
        B = (inverse(A + 1, N) - 1) % N
    except ValueError:
        B = -1

    print(B)

main()


Сходимость алгоритма инверсии логарифмическая, т.е. если A, B, N примерно 2^k, тогда
достаточно 2k+2 итерации максимум, т.е. максимум 66 итераций для 32-битного наибольшего
числа. Смотреть доказательство тут.