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

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)?

Ответ

Можно решить быстро без перебора, просто за счёт нахождения обратного по модулю 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-битного наибольшего числа. Смотреть доказательство тут