A^b mod m. Как сократить время выполнения ?

@Allivion · Регистрация: 04.04.2019

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

Здравствуйте! Рабочий код (вроде), но при проверке разные ошибки типа превышения времени ожидания и тп.
Помогите разобраться в чем проблема!

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <fstream>
using namespace std;
 
 
int pow_xy(int x, int y) {
    if (y == 0)
        return 1;
    else
        return x * pow_xy(x, y - 1);
}
 
int main() {
    int a, b, m;
    ifstream fin("input.txt");
    fin >> a >> b >> m;
    fin.close();
 
    ofstream fout("output.txt");
 
    fout<< (pow_xy(a, b) % m) << endl;
    fout.close();
    return 0;
}

@Allivion · 29.06.2019, 19:23 **[ТС]**

A^b mod m. Как сократить время выполнения ?

@Allivion · 29.06.2019, 19:24 **[ТС]**

wa - неправильный ответ
tl - тайм лимит
re - ошибка времени выполнения

@Pvt · 29.06.2019, 19:35

для чего рекурсия, y в цикл нельзя поставить?

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

C++
1
2
3
4
5
int pow_xy(int x, int y) {
  int r=1;
  for(int i=0; i<y; i++) r*=x;
  return r;
}

@Allivion · 29.06.2019, 19:39 **[ТС]**

Pvt, спасибо, но ничего не поменялось вообще =(

@Kuzia domovenok · 29.06.2019, 19:44

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

Рабочий код (вроде)

очевидно, код не рабочий, судя по неверным ответам в твоей табличке. Прежде чем оптимизировать какую-то непонятную "задачу", условия которой ты нам не говоришь, может для начала добьёшься в ней всех верных ответов? (Ну и условие может скажешь?!!?)

@Allivion · 29.06.2019, 19:47 **[ТС]**

Kuzia domovenok, условие : A^b mod m. Т.е. у нас есть 3 числа a,b,m. Нужно возвести A в степень B, затем поделить по модулю на m. ввожу например 2 3 10. Вывод 8. Все верно. Ввожу 2 3 8. Вывод 8. Тоже все правильно.
Не надо злиться, извините)

Байт · 29.06.2019, 20:26

Allivion, совершенно не нужно вычислять все значение a^b. После каждой операции надо рать его значение по модулю .
Например

C++
1
2
3
4
5
6
int pow_xy(int x, int y,int m) {
  int r=1;
   x %= m;
  for(int i=0; i<y; i++) r =  (r*x)%m;
  return r;
}

Конечно, тут тоже возможна оптимизация. Степень можно делить пополам. Но главное - получил результат - примени к нему тут же %m

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//Рекурсивно (и быстрее) это будет так
int pow_xy(int x, int y, int m) {
    x %=m;
    if (y == 0)
        return 1;
    else if (y == 1)
        return x;
    else {
        int z = pow_xy(x, y/2, m);
        z = (z*z)%m;
        if (y%2) z = (z*x)%m;
        return z;
    }
}

@zss · 29.06.2019, 20:51

Нашел простейший способ получить сразу остаток используя преобразование в double:

C++
1
2
3
4
5
long pow_xym(long a, long b, long m ) {
   long q = (long)((long double)a * (long double)b / (long double)m);
   long r = a * b - q * m;
   return (r + 5 * m) % m;
}

Источник
https://codeforces.com/blog/entry/1729

@Kuzia domovenok · 30.06.2019, 16:09

zss, тут возведение в степеь, а не умножение.

@zss · 30.06.2019, 17:38

Да, действительно.
Что-то я невнимательно прочитал условие.

Байт · 30.06.2019, 20:36

Да и с умножением все не так уж гладко. Все это имеет смысл, когда m² вылезает за сетку. Подход до смешного прост - сетку расширить. Но значительно интереснее использовать Китайскую Теорему об Остатках. То есть взять 2 взаимно простых простых числа, чье произведение превосходит m. Можно и три или четыре. Все посчитать по ихнем модулям, а потом восстановить.
https://ru.wikipedia.org/wiki/... 0%B0%D1%85
Теорема была сформулирована и доказана в 1247 году нашей эры, так что о качестве можете не беспокоиться

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	Установка Emscripten SDK (emsdk) и CMake на Windows для сборки C и C++ приложений в WebAssembly (Wasm) 8Observer8 30.01.2026 Чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. Система контроля версиями Git. . .	Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .

@Allivion 3 / 2 / 1 Регистрация: 04.04.2019 Сообщений: 158
	29.06.2019, 19:23 [ТС]
	0

@Allivion 3 / 2 / 1 Регистрация: 04.04.2019 Сообщений: 158
	29.06.2019, 19:24 [ТС]
	wa - неправильный ответ tl - тайм лимит re - ошибка времени выполнения 0

@Allivion 3 / 2 / 1 Регистрация: 04.04.2019 Сообщений: 158
	29.06.2019, 19:39 [ТС]
	Pvt, спасибо, но ничего не поменялось вообще =( 0

@Allivion 3 / 2 / 1 Регистрация: 04.04.2019 Сообщений: 158
	29.06.2019, 19:47 [ТС]
	Kuzia domovenok, условие : A^b mod m. Т.е. у нас есть 3 числа a,b,m. Нужно возвести A в степень B, затем поделить по модулю на m. ввожу например 2 3 10. Вывод 8. Все верно. Ввожу 2 3 8. Вывод 8. Тоже все правильно. Не надо злиться, извините) 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,532 Записей в блоге: 1
	30.06.2019, 16:09
	zss, тут возведение в степеь, а не умножение. 2

@zss Модератор 13771 / 10964 / 6491 Регистрация: 18.12.2011 Сообщений: 29,241
	30.06.2019, 17:38
	Да, действительно. Что-то я невнимательно прочитал условие. 1

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	30.06.2019, 20:36
	Да и с умножением все не так уж гладко. Все это имеет смысл, когда m² вылезает за сетку. Подход до смешного прост - сетку расширить. Но значительно интереснее использовать Китайскую Теорему об Остатках. То есть взять 2 взаимно простых простых числа, чье произведение превосходит m. Можно и три или четыре. Все посчитать по ихнем модулям, а потом восстановить. https://ru.wikipedia.org/wiki/... 0%B0%D1%85 Теорема была сформулирована и доказана в 1247 году нашей эры, так что о качестве можете не беспокоиться 2

A^b mod m. Как сократить время выполнения ?

Решение