Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
Вернуться
Тема: Модульная арифметика, деление чисел по модулю.
1
  1  Садуллоев Чафар, 04 января 2019 г. 12:30:47
      fh
  2  Хворых Павел, 04 января 2019 г. 9:06:21
      "При чём здесь уравнение b*x = a (mod m)?" - это определение деления.
Деление a/b определяется как вычисление числа x, которое после умножения на b даст a, ровно это и написано в уравнении. Вам надо по модулю, поэтому еще добавляется (mod m).
Важно отметить, что решений может быть несколько или не быть вообще.
  3  Яндулов Богдан, 03 января 2019 г. 21:08:12
      При чём здесь уравнение b*x = a (mod m)? Задача состоит в том, чтобы вычислить (A/BC)(mod M), где M - любое число. Также известно, что A делится без остатка на BC. Числа A,B,C большие, порядка 3000!.
  4  Тер-Саркисов Богдан Олегович, 03 января 2019 г. 21:02:06
      Частное решение можно получить как с помощью расширенного алгоритма Евклида, так и с помощью нахождения обратного элемента b'^(-1) по модулю m', так как gcd(b', m') = 1. Обратный элемент можно найти с помощью возведения b' в степень fi(m')-1, где fi(m') - функция Эйлера.
  5  Тер-Саркисов Богдан Олегович, 03 января 2019 г. 20:43:36
      Пусть есть задача найти решение уравнения b*x = a (mod m), где известны m, a, b (b, m - натуральные, a - целое неотрицательное). Задача сводится к решению линейного диофантового уравнения с двумя неизвестными: b*x + m*y = a, где x, y нужно найти. Пусть g = gcd(b, m). Сделаем подстановку b = b'*g, m=m'*g, то есть b'*g*x + m'*g*y = a. Или же g*(b'*x + m'*y) = a. Отсюда следует, что если a не делится на g, то уравнение решений не имеет. Иначе a' = a/g. Получили диофантово уравнение b'*x + m'*y = a', в котором gcd(b', m') = 1. Далее решаем его, получаем частное решение для x в диапазоне от 0 до m'-1.
  6  Яндулов Богдан, 03 января 2019 г. 19:55:00
      Хорошо известен способ для вычисления результата деления по простому модулю: заменяем деление умножением на обратный элемент по нашему простому модулю. Но что делать, если модуль не простой?
1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru