Почему модульное возведение в степень происходит неправильно, когда мы меняем тип данных переменной «u» с long long на int? - PullRequest
Новая
       42

Почему модульное возведение в степень происходит неправильно, когда мы меняем тип данных переменной «u» с long long на int?

0 голосов
/ 09 июля 2019

Когда тип данных переменной "u" длинный, модульное возведение в степень работает хорошо, но когда оно изменяется на int, оно дает неправильные ответы.

Например, когда (2,447,1e9 + 7) передаются в качестве аргументов"long long u" дает 941778035 в качестве ответа, но "int u" дает 0 в качестве ответа.Функции следующие: - 

int modpow(int x, int n, int m) {  //to calculate x^n%m
    if (n == 0) return 1%m;
    long long u = modpow(x,n/2,m);
    u = (u*u)%m;
    if (n%2 == 1) u = (u*x)%m;
    return u;
}

int modpow(int x, int n, int m) {  //to calculate x^n%m
    if (n == 0) return 1%m;
    int u = modpow(x,n/2,m);
    u = (u*u)%m;
    if (n%2 == 1) u = (u*x)%m;
    return u;
}

int main(){    //used as main in program with x = 2 and m = 1e9+7 and n is given by user
   int n, m = 1e9+7;
   cin>>n;
   int pow = modpow(2,n,m);
   cout<<pow;
   return 0;
}

1 Ответ

0 голосов
/ 09 июля 2019

Думайте о modpow(1e9, 2, 1e9+7)

if (2 == 0) // no
int u = modpow(1e9, 1, 1e9+7);

  if (1 == 0) // no
  int u = modpow(1e9, 0, 1e9+7);

    if (0 == 0) return 1;

  int u = 1;
  u = 1; // (1*1) % (1e9+7)
  if (1 % 2 == 1) u = 1e9; // (1 * 1e9) % (1e9+7)

int u = 1e9;
u = (1e9 * 1e9)%(1e9+7); // OUCH!

1e9 * 1e9 переполняется, если int u имеет ширину всего 32 бита, что равно в большинстве современных компьютерных сред (см. https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models)

...