Китайская теорема об остатках


Отправить решение Решать в редакторе

Сложность: 40%
Очки: 100 (частичный балл)
Ограничение по времени: 1.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Китайская теорема об остатках

Найдите наименьшее целое x ≥ 0, для которого одновременно выполняется x ≡ rᵢ mod mᵢ для всех i. Модули не обязательно взаимно просты.

Ввод. В первой строке n (1 ≤ n ≤ 20). В следующих n строках пары rᵢ, mᵢ (0 ≤ rᵢ < mᵢ ≤ 10⁹). Гарантируется, что НОК всех модулей не превосходит 10¹⁸.

Вывод. Число x или -1, если решения нет.

Пример 1

Ввод:

2
1 4
3 6

Вывод:

9
Пример 2

Ввод:

2
1 4
2 6

Вывод:

-1

Комментарии

Еще нет ни одного комментария.