Задача №113568. Слон
Слон постоянно шалит в своей школе. На уроках ему становится скучно, и он начинает хулиганить. Учитель решил успокоить слона, поэтому дал ему очень сложную математическую задачу.
Учитаель дал слону арифметическое выражение A и числа P и M . Слону надо ответить на такой вопрос: "Каково минимальное неотрицательное значение переменной x в выражении A , такое что остаток от деления A на M равно P ?". Гарантируется, что решение всегда существует.
Кроме того, после применения законов распределения к выражению A , x содержится в A только в первой степени.
В первой строке содержится выражение A ( 1 ≤ | A | ≤ 10 5 ). Вторая строка содержит два целых числа P и M ( 0 ≤ P < M ≤ 10 6 ). A состоит только из символов +, -, *, (, ), x и цифр от 0 до 9. Каждый оператор +, -, * применяется ровно к двум значения, умножения всегда обозначены явно.
Выведите одно число – ответ на задачу
Пояснение к первому примеру:
(5 + 3 + x ) mod 10 при x = 0 равно 8.
(5 + 3 + x ) mod 10 при x = 1 равно 9. Значит, ответ x = 1 .
5+3+x 9 10
1
20+3+x 0 5
2
3*(x+(x+4)*5) 1 7
1