Длинные числа в C++

Question

У меня есть эта программа в Python:

# ... 
print 2 ** (int(input())-1) % 1000000007 

Проблема заключается в том, что эта программа работает долгое время на больших количествах. Я переписал свой код с помощью C++, но иногда у меня неправильный ответ. Например, в коде Python для номера 12345678 у меня есть 749037894 и его правильно, но на C++ у меня есть -291172004.

Это код C++:

#include <iostream> 
#include <cmath> 
using namespace std; 
const int MOD = 1e9 + 7; 

int main() { 
    // ... 
    long long x; 
    cin >> x; 
    long long a =pow(2, (x-1)); 
    cout << a % MOD; 
} 

Answer 1

Как уже упоминалось, ваша проблема заключается в том, что для большого экспонента у вас есть целочисленное переполнение.

Чтобы преодолеть это, помните, что модульное умножение имеет такое свойство, что:

(A * B) по модулю C = (A мод C * B мод C) мод C

А потом вы можете реализовать функцию e для функции power p modulo m, используя схему быстрого возведения в степень. не Предполагая, что никаких отрицательных сил:

long long powmod(long long e, long long p, long long m){ 
    if (p == 0){ 
     return 1; 
    } 
    long long a = 1; 
    while (p > 1){ 
     if (p % 2 == 0){ 
      e = (e * e) % m; 
      p /= 2; 
     } else{ 
      a = (a * e) % m; 
      e = (e * e) % m; 
      p = (p - 1)/2; 
     } 
    } 
    return (a * e) % m; 
} 

Обратите внимание, что остаток берется после каждого умножения, поэтому нет переполнения не может произойти, если умножение одного не переполнение (и это верно для 1000000007 в m и long long).

Answer 2

Вы, кажется, иметь дело с положительными числами, и те переполнены число битов вы выделенных для их хранения. Также имейте в виду, что существует разница между Python и C/C++ в том, как вычисляется модуль по отрицательному значению. Для того, чтобы получить подобный расчет, вам нужно будет добавить Modulo к значению, так что это положительный, прежде чем принимать по модулю, который, как она работает в Python:

cout << (a+MOD) % MOD; 

Вы, возможно, придется добавить MOD п раз, пока временное значение положительно, прежде чем принимать его по модулю.

Answer 3

Как уже упоминалось многими другими ответами, ваша проблема заключается в переполнении целого числа.

Вы можете сделать, как предложено deniss, и реализовать свои собственные функции modmul() и modpow().

Если, однако, это часть проекта, который потребует большого количества вычислений с очень большими числами, я бы предложил использовать «большую библиотеку номеров», например GNU GMP или mbedTLS Bignum library.

Answer 4

В C++ различные фундаментальные типы имеют фиксированные размеры. Например, long long обычно имеет ширину 64 бит. Но ширина зависит от типа системы и других факторов. Как было предложено выше, вы можете проверить climits.h за пределы вашей конкретной среды.

Повышение 2 к власти 12345677 предполагает смещение двоичного числа 10 оставленного 12345676 бит, которые не помещаются в 64 битом long long (и я подозреваю, что вряд ли уместится в большинстве long long реализации).

Другим фактором, который следует учитывать, является то, что pow возвращает double (или long double) depending on the overload used.Вы не говорите, какой компилятор вы используете, но, скорее всего, вы получили предупреждение о возможном усечении или потере данных, когда результат вызова pow присваивается переменной long longa.

Наконец, даже если pow возвращается длинный двойной Я подозреваю, что показатель 12345677 слишком велик, чтобы хранить в long double так pow, вероятно, возвращая положительную бесконечность, который затем получает усеченный до некоторой комбинации битов, которые будут соответствовать в long long. Вы можете, конечно, проверить это, введя промежуточную переменную long double, чтобы получить значение pow, которое затем можно было бы проверить в отладчике.