дальше по индукции: 1. 201 = 20 == 20 mod 42 2. утверждается, что если 20N == 20 mod 42, то 20N+1 == 22 mod 42 если 20N == 22 mod 42, то 20N+1 == 20 mod 42 3. 4. 202009 = 20 mod 42
тебе надо вычислить 384873*473884 mod 3 если напрямую умножить, то получится большое число, с которым трудно работать. но достаточно взять остатки от множителей, и работать уже с числами, меньшими делителя.
тут по индукции разворачивается такая картина: 20N+1 mod 42 == 20N*20 mod 42 = (20N mod 42)*20 mod 42 при этом значение 20N mod 42 считается как бы известным из прошлых шагов индукции.
in your face, meatbag! 🙂
когда меня учили решению таких задач, таких мощных ЭВМ ещё не было. Так что нечестно. 🙂
Тогда уж Mod[Pow[314, 2009],42] :)
ну он и просто 3142009 mod 42 понимает
3142009 mod 42 == 202009 mod 42
дальше по индукции:
1. 201 = 20 == 20 mod 42
2. утверждается, что
если 20N == 20 mod 42, то 20N+1 == 22 mod 42
если 20N == 22 mod 42, то 20N+1 == 20 mod 42
3.
4. 202009 = 20 mod 42
а можешь разжевать, пожалуйста?
Или ктонибудь!
ну вот смотри, есть общее правило:
(A*B) mod N == (A mod N)*(B mod N) mod N
тебе надо вычислить 384873*473884 mod 3
если напрямую умножить, то получится большое число, с которым трудно работать. но достаточно взять остатки от множителей, и работать уже с числами, меньшими делителя.
тут по индукции разворачивается такая картина:
20N+1 mod 42 == 20N*20 mod 42 = (20N mod 42)*20 mod 42
при этом значение 20N mod 42 считается как бы известным из прошлых шагов индукции.
3142009 / 42 = 3142008*314 / 42 = 3142008*157 / 21 = 3142006*157*314*314 / 21 = 3142006*3*157(1*2*2) / 21 = 3142006*157(4) / 7 = 3142004*157(8) / 7 = 3142004*157(7)*157/7 = 3142004 * 157
Но это какойто ебаный метод. Решал всё в уме, и както сонно, потому может быть косяк.
БЛЯТЬ, ВЫ ПОЧТИ ВСЕ ТУТ УПОРОТЫЕ, ОСТАТОК ОТ ДЕЛЕНИЯ НА 42
МЕНЬШЕ ЧЕМ 42! я идиот! убейте меня, ктонибудь!
20
Кажется, действительно, пиздец, ошибся.
Бля, я задание не прочитал(99
Это же Анч уже писал про 42, что 42 число в записи п=3.1415926 тоже 42.
он писал несколько иное. 🙂
откуда берем 22?