0

Доброго дня, столкнулся с очень нестандартной проблемой. Возвожу число в степень, например, 3 в степень 605, в итоге получается 4,553644 × 10 в стеепени 288. Потом беру mod этого числа на другое число и в итоге получается маленькое число. Так вот можно ли как-то в цикле возводить число в степень и делать mod т.к. присвоить такое огромное число какой-то переменной не получается?

 buffer = pow(alf_numbers[i],e);
 key[i] = buffer % n;

в буфере получается 4,553644 × 10 в стеепени 288

1 ответ 1

3

вычисляем a ^ b mod m

int r = 1;

for (int i = 1; i < b; i++) {
  r = r * a;
  r = r % m;
}

cout << r << endl;

если степени большие, то можно пользоваться быстрым возведением в степень.

берем готовый алгоритм возведения в степень, исправляем ошибки и доделываем под нужды

#include <iostream>
using namespace std;
//быстрое возведение в степень
int bpow(int x, int n, int m)
{
  int count=1;
  if (!n) return 1;
  while (n) {
    if (n%2==0) {
      n/=2;
      x*=x;
      x %= m;
    } else {
      n--;
      count*=x;
      count %=m;
    }
  }
  return count % m;
}
//главная функция
int main() {
  int x; int n; int m;
  cout<<"Основание > "; cin>>x;
  cout<<"Степень > "; cin>>n;
  cout<<"модуль > "; cin >> m;
  cout<<x<<"^"<<n << " % " << m <<"="<<bpow(x, n, m);
  return 0;
}
4
  • 1
    @KoVadim можно только пояснить ТС, что возведение в степень в общем случае -- это экспонента произведения на логарифм? И, соответственно, вычисления сугубо приближённые, после их приведения к целому результат вполне может удивить.
    – alexlz
    12 авг 2014 в 7:42
  • 1
    А не имеет значения, логарифм там или просто циклом. Здесь проблема в том, что количество разрядов сильно ограничено.
    – KoVadim
    12 авг 2014 в 7:48
  • @KoVadim не понял. Возведение целого числа в целую степень с использованием логарифма и экспонененты -- это уже совсем отдельная песня, которая и даёт странный для новичка результат.
    – alexlz
    12 авг 2014 в 15:59
  • для новичка, который ещё в школе не прошел логарифмы. А так просто нужно сказать, что в большинстве языков программирование есть pow, который работает через экспоненту-логарифм и есть pow, который делает честные умножения.
    – KoVadim
    12 авг 2014 в 16:32

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.