Обратный элемент
(Время: 1 сек. Память: 16 Мб Сложность: 73%)
Кольцо вычетов – система операций сложения и умножения над целыми числами по модулю m. Все операции и их результат представляются числами диапазона от 0 до m-1.
Обратный элемент числа a в кольце вычетов по модулю m – это такое число a-1, что a•a-1=1.
Требуется определить обратный элемент для числа a в кольце вычетов по модулю m.
Входные данные
Входной файл INPUT.TXT содержит целые числа a и m – число и основание кольца вычетов (0 ≤ a < m ≤ 109, m>1).
Выходные данные
В выходной файл OUTPUT.TXT выведите значение обратного элемента для числа a, если он существует в кольце вычетов по модулю m. В противном случае выведите «No solution».
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 7 10 | 3 |
| 2 | 3217 16384 | 13425 |
| 3 | 4 16 | No solution |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
