ур-ние Опции

[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


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

[Orion]

А просто циклом от 0 до M проверять все возможные X не подходит?

[klem4]

Перебор врядли .. проверь вот это :

var
   a,b,m : integer;
begin
   readln(a); readln(b); readln(m);
   if (m + b) mod a <> 0 then writeln('no')
    else writeln((m + b) div a);
   readln;
end.

А просто циклом от 0 до M проверять все возможные X не подходит?

Ага, если M = 10 ^ 9 = 1000000000 :D

Сообщение отредактировано: klem4 - 16.01.2006 22:40

[Antonina]

Перебор врядли .. проверь вот это :

var
   a,b,m : integer;
begin
   readln(a); readln(b); readln(m);
   if (m + b) mod a <> 0 then writeln('no')
    else writeln((m + b) div a);
   readln;
end.

Ага, если M = 10 ^ 9 = 1000000000 :D

klem4? не всегда работает. тесты дать не могу т.к. сам их не знаю.

[klem4]

приведи хотя бы те на которых не работает, подумаем еще .. решение очень простое должно быть, я уверен

Сообщение отредактировано: klem4 - 16.01.2006 22:36

[Гость]

приведи хотя бы те на которых не работает, подумаем еще .. решение очень простое должно быть, я уверен

Я не знаю мх. мы тут с другом решаем напару. используя онлайн-тестинг.

[klem4]

Отлично, что за онлай тест ? ссылку дал бы чтоли, у нас телепатов нет.

[Гость]

сссори,но я она,А НЕ ОН. к сожалению он не доступен для москвы. тока для нашего региона.

[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

[Pola]

ax mod m = b
ax-b mod m = 0
ax-b = km k-целое надо подобрать, чтобы найти x

x:=(k*m+b) div a

Код

var
   a,b,m,k : integer;
begin
   readln(a,b,m);
   k:=1;
   while (k*m+b) mod a <>0 do inc(k);
   write ((k*m+b) div a);
   readln;
end.

[volvo]

Pola, вводим в приведенную тобой программу следующие данные:
A = 3; B = 200; M = 156000
Что должно быть в результате?

-1...

Твоя программа возвращает 8376 при запуске в TP, и -715815464 под FPC...

7. Проверяйте программы перед тем, как запостить их!!!

[Pola]

Ну вот...
то дай ошибку поикать, то проверяй сама

Ты меня конечно извини, но если ты уже ищешь у всех в программах ошибки, а сама при этом их допускаешь - то где логика?


Какие будут предложения для проверки несуществования х?

чем нибудь k ограничим?

Я тебя конечно извиняю, volvo, но я не говорила, что сама их не допускаю
В одной из тем, даже просила поискать...


я так думаю: не существует, если
1) b>=m
2) ? какие еще ?

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

[Pola]

так лучше?

var
   a,b,m,k : longint;
begin
   readln(a,b,m);
   if (0<=a) and (b<m) then
   begin
     k:=1;
     while ((k*m+b) mod a <>0)  and ((k*m+b) div a < m) do inc(k);
     if ((k*m+b) mod a = 0) and ((k*m+b) div a < m) then write ((k*m+b) div a) else write(-1); 
   end
   else write(-1);
end.

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