ур-ние Опции

[Antonina]

Даны три числа A, B и M (0<=A,B<M). Найдите такое X (0<=X<M), что A*X имеет остаток B при делении на M.

Входные данные
Даны целые A, B и M (1<=M<=10^9).

Выходные данные
Выведите любое Х удовлетворяющее условию задачи. Если такого не существует -- выведите -1.

Пример

Ввод

3 2 10



Вывод

4


как решать ума не приложу.

[klem4]

Чот я запутался

Смотрите берем такой вариант

a = 3; b = 1; m = 7;

aX mod m = b;
3x mod 7 = 1;
x = 5;

Далее рассуждение :

ax mod m = b;
(ax - b) = ax div m * m <=> (3*5 - 1) = (3*5 div 7) * 7 <=> 14 = (15 div 7) * 7 <=> 14 = 2 * 7;
ax - ax div m * m = b; <=> 15 - 14 = 1

а вот дальше нестыковка ...

x = b / (a - a div m * m); так как a div m = 3 div 7 = 0, знаменатель равен просто a, и х получается = 1/3

пора спать.

Сообщение отредактировано: klem4 - 17.01.2006 0:14