Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #11  
Старый 24.05.2009, 00:58
_persicum_

 
Сообщений: n/a

Корректный вариант mod 7 используя признак делимости таков

Умножаем последнюю цифирь на 5 и прибавляем
12345 mod 7 = 1234 + 25 = 1259 = 125 + 45 = 170 = 17 + 0 = 17 = 3
Результат требует коррекции, так как умножен на 5 три раза.
Теперь нужно умножить трижды на мультипликативный обратный к 5, а это по совпадению тоже 3

3*3 = 9 = 2 = 2*3 = 6 = 6*3 = 18 = 18 - 14 = 4

Уфф!!!
Наверно проще было поделить, но частное не записывать, а сразу выписывать остаток от лидирующих цифр, что тоже составляет отдельный алгоритм

12345 = 5345 = 445 = 25 = 4 - получилось в уме!
  #12  
Старый 25.05.2009, 08:43
_persicum_

 
Сообщений: n/a

Придумал, как усовершенствовать метод mod 7 с домножением последней цифры на 5. Число этих домножений должно быть кратным шести!

В предыдущем посте за три домножения на 5 получилось 17. Проделываем это еще три раза

17 = 1 + 35 = 36 = 3 + 30 = 33 = 3 + 15 = 18 = 4

Теперь правильно и без мультипликативного обратного.

Держу пари что кореша автора топика так не умеют брать остаток mod 7
  #13  
Старый 25.05.2009, 11:58
гость

 
Сообщений: n/a

Я вот еще придумал приём, основанный на св-ве: n mod m = (n mod mk) mod m, где k - целое, k>=1.

Допустим надо взять n mod 5, тогда достаточно вычислить t=n mod 10 (это последняя цифра n), и результат будет равен t mod 5.

Другой пример: n mod 25 = (n mod 100) mod 25 = (последние две цифры n) ьщв 25

Еще: n mod 225 = (n mod 1000) mod 225 = (три последние цифры n) mod 225
  #14  
Старый 25.05.2009, 11:59
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Еще: n mod 225 = (n mod 1000) mod 225 = (три последние цифры n) mod 225
s/225/250/g
  #15  
Старый 25.05.2009, 12:24
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>Еще: n mod 225 = (n mod 1000) mod 225 = (три последние цифры n) mod 225

продемонстрируйте на числе n=1225
  #16  
Старый 26.05.2009, 11:02
_persicum_

 
Сообщений: n/a

А я все тащусь от изобретенного мною метода mod 7.
Для закрепления материала вычислим 1234567654321 mod 7 методом умножения последней цифры на 5.

1234567654321
123456765437
12345676578
1234567697
123456804
12345700
1234570
123457
12380
1238
163
31

Уже сделали 11 шагов. Поскольку нужно, чтобы число шагов было кратно шести, делаем еще 1 штрафной шаг.

8, а это 8-7=1 Уррра!!!

Вывод: 1234567654321 mod 7 = 1

>Я вот еще придумал приём, основанный на св-ве: n mod m = (n mod mk) mod m

Хорошее дополнение! Оно неявно используется при определении чет-нечет и делимости на 5, 25, 4, 3 и т.д.

>продемонстрируйте на числе n=1225

Ребяты, не все сразу! Вы сначала определитесь, что вам милей, 250 или 125
  #17  
Старый 27.05.2009, 20:01
_persicum_

 
Сообщений: n/a

>А я все тащусь от изобретенного мною метода mod 7.

А можно еще прощще =)))
1234567654321 mod 7 = 1 - 234 +567 - 654 + 321 = 1.

Это потамушта 1001=7*11*13
  #18  
Старый 08.06.2009, 18:44
гость

 
Сообщений: n/a

Несколько запутался...
Встретилась вот такая запись:

2^(-1) mod 7

Чему она может быть равна?
  #19  
Старый 08.06.2009, 19:14
zhekas

 
Сообщений: n/a

2^(-1) mod 7 = 4, так (2*4) mod 7 = 1
  #20  
Старый 13.06.2009, 13:49
_persicum_

 
Сообщений: n/a

А как это вы догадались, что именно 4, а не 3, не 5?

скажем, 2^(-1) mod 257 сколоко будет?
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вывести значение целочисленного выражения, заданного в виде строки S в delphi SergeyHelpMe Математические алгоритмы 5 12.06.2008 12:59
не пойму условия задачи indolent Задачи 2 19.05.2008 07:32
Распознование регулярного выражения Programmer Реализация, исходники, языки 3 29.04.2008 17:23