Question

Как быстро брать остаток от деления ?
Смотрю видео курс по подготовке к ЕГЭ по информатике ( Андрея Рогова ).
Есть ли какой то алгоритм как брать остаток от деления устно ( в видео за пару секунд он делит по модулю любое число на 3, 4 , 8 ).
Я делю число на 3 где то секунд 30, возможно больше, очень много трачу времени на столбики, при том мне не важен результат деления, а именно отстаток.

Answer 1

Не знаю, как с алгоритмом, а находить остатки деления на 3, 4, 8 можно по признакам делимости.

1) n mod 3

Число делится на 3, если сумма его цифр кратна трем.

Пусть дано число 373412. Его сумма цифр 3+7+3+4+1+2 = 20. 20 на 3 не делится, но делится 18 (ближайшее меньшее). Разница 2 - это и есть нужный ответ. 373412 мод 3 = 2

2) n mod 4

Число делится на 4, если две его последние цифры нули или делятся на 4. Пусть дано число 37535627345. Его две последние цифры 45. 45 на 4 не делится, но делится 44. Разница 1. Это и есть ответ. 37535627345 mod 4 = 1

3) n mod 8

Самый сложный вариант. 8 = 4х2. Как и для случая получения остатка по mod 4 получаем остаток по двум последним цифрам. Далее, если третья справа цифра нечетная, добавляем к результату 4.

45684373 mod 8. Для числа 73 находим остаток от деления на 4. На 4 делится 72, так что остаток тут 1. Перед 73 стоит нечетная цифра 3, поэтому добавляем 4, итого 1+4=5. 45684373 mod 8 = 5.

878746345242 mod 8. 42 mod 4 =2 (уже не буду подробно писать). Перед 42 стоит 2 - четное число. Результат не меняем. 878746345242 mod 8 = 2.

Так что ничего волшебного.