时间戳

首页 > 解决方案 > 当我们将变量“u”的数据类型从 long long 更改为 int 时，为什么模幂运算会出错？

c++ - 当我们将变量“u”的数据类型从 long long 更改为 int 时，为什么模幂运算会出错？

问题描述

当变量“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;
}

标签： c++integerlong-integermodular-arithmetic

解决方案

想一想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）

推荐阅读