Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
85. Китайская армия
Китайская теорема об остаткахОлимпиадные задачи на русском языке
| 05/05/2002 | Региональная олимпиада Информатика-2002 (2) |
| 21/09/2006 | Практическое занятие 2 (C) |
| 08/10/2011 | Занятие 3 (B) |
| 03/03/2015 | Занятие 15 (B) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Китайский главнокомандующий решил подсчитать точное количество солдат в своей армии, пользуясь китайской теоремой об остатках. Он несколько раз расставлял солдат шеренгами по `n` человек и записывал количество человек в последней неполной шеренге. Известно, что количество солдат в китайской армии не меньше `K`. Используя эту информацию, определите минимально возможное количество солдат в китайской армии.
Ввод
Во входном файле в первой строке указаны два целых числа `P` и `K`, разделенные пробелом – число построений и минимально допустимое число солдат в китайской армии (`1≤P≤19,\ 1≤K≤10^9`). Далее следует `P` строк, содержащих по два целых числа `n` и `m`, разделенных пробелом – количество человек в шеренге и количество человек в последней неполной шеренге или 0, если все шеренги полны (`2≤n≤20,\ 0≤m<n`).
Вывод
В выходной файл вывести минимально возможное количество солдат в китайской армии.
Пример ввода
2 10 3 2 4 1
Пример вывода
17
