имея перед собой компьютер это сложно посчитать?

_________________
email/IM/SMS/Talk/Hangouts:

если мне не изменяет память 2 во второй степени это 2*2,в третей-2*2*2 и так далее.следовательно разбиваем 2 в степени 1000000 на ряд 2в степени 10*2 в степени 10 и так далее в количестве 6 множителей-по числу нулей в 1000000 т.е. 6 раз.далее тупо считаем 2 в степени 10 и делим на 77-в остатке 23 ,далее перемножаем 23 на 23 6 раз и все делим на 77 и в остатке у меня получилось 0,9998979,,,-видимо в остатке ровно 1-как то так,вообще эта задачка из школьной программы когда проходят степени

все равно регистра не хватит тупо перемножать-в этом то и фокус

Нет. Интересна сама логика подсчета. Задача изначально не столько на математику, сколько на логику.

_________________
Даёшь тёплые ламповые Негонки!

2^1.000.000=(2^1.000)*1000=((2^10)*100)*1000
2^10=1024
1024 mod 77 = 23
23*100 = 2300
2300 mod 77 = 67
67*1000 = 67000
67000 mod 77 = 10

ответ 10 ))

_________________
Никогда ничего не замышляйте против России, потому что на каждую вашу хитрость она ответит своей непредсказуемой глупостью. (Отто фон Бисмарк)

лихо в первой строке разложил степень чтож дальше не разложил-получилось бы 2*1000000 дальше соответственно не совсем прально вроде.так мало помалу придем к решению

2^1.000.000 = 2^(1.000*1.000)

Марат, где будешь хранить миллион-разрядное двоичное число? У меня проц 64-разрядный
Вообще эта задачка из Теории чисел. Криптографы на ВМК изучают и, наверное, ещё мехматовцы.

a^(b+c)=(a^b)*(a^c)
не так ли?

ага, дошло, напутал
т.е
2^1.000.000=(2^1000)^1000=((2^10)^100)^1000

_________________
Никогда ничего не замышляйте против России, потому что на каждую вашу хитрость она ответит своей непредсказуемой глупостью. (Отто фон Бисмарк)

_________________
Мы уже победили, просто это еще не так заметно.

ввиду того, что в задаче не ставился вопрос о быстродействии, то никто не мешает хранить все цифры в оперативной памяти/файловой системе/бд.

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

_________________
email/IM/SMS/Talk/Hangouts:

23

a^n mod d = ((a mod d) ^ n) mod d

Ahill прав, будет 23.

Значит так: 2^1000000=1024^100000=(n*77+23)^100000, где n=13. Раскладываем это в бином Ньютона (уверен, все проходили его на первом курсе). Получаем:
(n*77+23)^100000=(n*77)^100000+100000*23*(n*77)^99999+...+100000*23^99999*(n*77)+23^100000
Все слагаемые кроме последнего остатка от деления на 77 не дают.

Рассмотрим 23^100000=(23^10)^10000=(n*77+23)^10000, где n=538006639138. Снова раскладываем в бином Ньтона, получаем что остаток дает только 23^10000

............................................................
............. что остаток дает только 23^10 и этот остаток равен как раз 23

_________________
Go hard -> Go pro -> Go crazy

2^(10^6) = (2^10)^(10^5) = 1024 ^(10^5)
1024 ^(10^5) mod 77 = 23 ^(10^5) mod 77 = (23^10) ^(10^4) mod 77;
(23^10) mod 77 = 23; => (23^10) ^(10^N) mod 77 = (23^10) ^(10^N-1) mod 77 = ... = 23

Ребят, тут ФЛЕЙМ! Причем счастливый

_________________
о себе

Рецепт. Как в домашних условиях приготовить вкусный напиток из кактуса.
Пункт 1. Налить почти полный стакан водки.
Пункт 2. Выкопать кактус из горшка. Аккуратно ножницами удалить все колючки и корни.
Пункт 3. Взять кактус в руку, сжать его, и всю получившуюся жидкость выдавить в стакан.
Пункт 4. Содержимое стакана тщательно перемешать.
Пункт 5. Вкусный напиток готов. Выпить сразу, крупными глотками.
Примечание. Если у вас дома нет кактуса, то пункты 2, 3, 4 можно исключить.

_________________

веломеханик 89053125244 телефон и вацап
группа вконтакте