Вычислить n-ую сверхстепень двойки по модулю m

@Gardikind · Регистрация: 14.10.2015

Студворк — интернет-сервис помощи студентам

Назовем значение выражения 22n n-ой сверхстепенью числа 2. Таким образом, например, третья сверхстепень числа 2 равна 223 = 28 = 256.

Ваша задача – вычислить n-ую сверхстепень двойки по модулю m.

Входные данные

Входной файл INPUT.TXT содержит два целых числа: n (0 ≤ n ≤ 105) и m (2 ≤ m ≤ 104).

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

@Puporev · 14.10.2015, 10:17

Ума нет даже задание нормально написать, сам-то понимаешь что написал? В оригинале так же?

Добавлено через 2 минуты

Сообщение от Gardikind

223 = 28 = 256.

Сообщение от Gardikind

n (0 ≤ n ≤ 105) и m (2 ≤ m ≤ 104).

Вот это что?

@Gardikind · 14.10.2015, 10:33 **[ТС]**

2^(2^n) 2^(2^3) 2^8 10^5 10^4

Добавлено через 12 минут
извиняюсь
копируя забыл что степень будет показана не корректно
получается что двойка в степени 2 и в стпени n (к примеру если n = 3 то получится что двойка будет в степени 8 )

@JuriiMW · 14.10.2015, 10:35

$https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{{2}^{n}}$ по модулю $https://www.cyberforum.ru/cgi-bin/latex.cgi?m$

Решение, как говорится, в лоб:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
begin
  var n : Integer;
  var m : Integer;
  ReadLn(n, m);
  var p := BigInteger.Pow(2, n);
  var r := 1;
  while BigInteger.Compare(p, 0) = 1 do
    begin
      p -= 1;
      r := (r * 2) mod m;
    end;
  WriteLn(r);
end.

@msz301005 · 04.06.2018, 21:03

JuriiMW, в лоб не зайдет, там 105 - это 10^5, а 104 - это 10^4

Добавлено через 2 минуты
Puporev, там как бы 2^(2^3) = 2^8 = 256. Эта задача из acmp и там степень ставят так, как пишут в школе, то есть это число выше того числа.

@JuriiMW · 05.06.2018, 05:33

msz301005, вам не лень было поднимать тему почти трёхлетней давности, чтобы ляпнуть глупость?

Во-первых, мой код „зайдёт“ и ещё как! И даже на значениях больших миллиона…

А во-вторых, неужели вы считаете Puporev таким глупым и наивным?

Ну и в-третьих, внизу страницы, для таких как вы, имеется редактор формул!

@volvo · 05.06.2018, 10:30

О том, что в изначальной постановке времени на задачу отводится 1 секунда, ТС благоразумно промолчал...

Кстати, совсем не обязательно делать цикл (с циклом алгоритм будет работать больше секунды, понятно), в классе BigInteger есть ModPow, который сразу возводит в степень по модулю:

Pascal
1
2
3
4
5
begin
  var n, m : integer;
  ReadLn(n, m);
  writeln(BigInteger.ModPow(2, BigInteger.Pow(2, n), m)); // оба тестовых примера отрабатывают как положено
end.

Ответ при n = 100000 и m = 9998 (практически - граничные требования) выдается мгновенно: 8844

@msz301005 · 21.06.2018, 09:09

JuriiMW, Я писал уже такое решение, и у меня было превышение времени на 4 тесте.

@falkramm · 03.08.2019, 22:54

народ подскажите если можно как это реализовать в с++

@Sun Serega · 04.08.2019, 00:55

Декомпилируйте BigInteger (или ещё как то получите его исходники) и переведите на C++.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@Gardikind 0 / 0 / 0 Регистрация: 14.10.2015 Сообщений: 5

	Вычислить n-ую сверхстепень двойки по модулю m 14.10.2015, 10:12. Показов 7033. Ответов 9 Метки нет (Все метки) Назовем значение выражения 22n n-ой сверхстепенью числа 2. Таким образом, например, третья сверхстепень числа 2 равна 223 = 28 = 256. Ваша задача – вычислить n-ую сверхстепень двойки по модулю m. Входные данные Входной файл INPUT.TXT содержит два целых числа: n (0 ≤ n ≤ 105) и m (2 ≤ m ≤ 104). Выходные данные В выходной файл OUTPUT.TXT выведите ответ на задачу. 0

@Gardikind 0 / 0 / 0 Регистрация: 14.10.2015 Сообщений: 5
	14.10.2015, 10:33 [ТС]
	2^(2^n) 2^(2^3) 2^8 10^5 10^4 Добавлено через 12 минут извиняюсь копируя забыл что степень будет показана не корректно получается что двойка в степени 2 и в стпени n (к примеру если n = 3 то получится что двойка будет в степени 8 ) 0

@msz301005 0 / 0 / 1 Регистрация: 18.02.2018 Сообщений: 112
	04.06.2018, 21:03
	JuriiMW, в лоб не зайдет, там 105 - это 10^5, а 104 - это 10^4 Добавлено через 2 минуты Puporev, там как бы 2^(2^3) = 2^8 = 256. Эта задача из acmp и там степень ставят так, как пишут в школе, то есть это число выше того числа. 0

@JuriiMW 5095 / 2661 / 2355 Регистрация: 10.12.2014 Сообщений: 10,060
	05.06.2018, 05:33
	msz301005, вам не лень было поднимать тему почти трёхлетней давности, чтобы ляпнуть глупость? Во-первых, мой код „зайдёт“ и ещё как! И даже на значениях больших миллиона… А во-вторых, неужели вы считаете Puporev таким глупым и наивным? Ну и в-третьих, внизу страницы, для таких как вы, имеется редактор формул! 0

@msz301005 0 / 0 / 1 Регистрация: 18.02.2018 Сообщений: 112
	21.06.2018, 09:09
	JuriiMW, Я писал уже такое решение, и у меня было превышение времени на 4 тесте. 0

@falkramm 0 / 0 / 0 Регистрация: 27.07.2019 Сообщений: 8
	03.08.2019, 22:54
	народ подскажите если можно как это реализовать в с++ 0

@Sun Serega 2355 / 1458 / 526 Регистрация: 07.04.2017 Сообщений: 4,798
	04.08.2019, 00:55
	Декомпилируйте BigInteger (или ещё как то получите его исходники) и переведите на C++. 0