Задача 102955

Тема:    [ Длинная арифметика как инструмент ]

Сложность: 3+ Классы: Название задачи: Длинное равенство.

Условие

Во входном файле записано равенство вида A = B, где A и B – это выражения, содержащие сколь угодно длинные целые числа и знаки операций +, - (бинарный и унарный) и *. Выражения не содержат скобок. Требуется проверить выполнение заданного равенства и вывести в выходной файл результат проверки в форме «Да, выполняется» или «Нет, не выполняется».
Длина входного файла данных не превосходит 60 килобайт. Числа и знаки операций в выражении могут разделяться пробелами и/или символами перевода строки.

Пример входного файла
2
                * 43 = 86

Пример выходного файла
Да, выполняется

Решение

Скачать архив тестов и решений

Поскольку в результате вычислений могут получаться очень большие числа, то точно подсчитать значение каждого из выражений A и B за отведенное для работы программы время нереально. Однако относительно легко сравнить левую и правую части по какому-то модулю. Если провести такую проверку для достаточно большого набора взаимно простых модулей, то можно с большой вероятностью дать правильный ответ.

Источники и прецеденты использования

книга
предмет	информатика
Автор	Беров В., Лапунов А., Матюхин В., Пономарев А.
Название	Особенности национальных задач по информатике
Издательство	Триада-С
Год издания	2000
глава
Номер	6
Название	Задачи на разные темы
Задача
Номер	10