为什么将模幂运算中变量u的类型从long long改为int会出错？

这个问题的核心原因是整数溢出，咱们一步步拆解来搞明白：

问题重现 #

当调用modpow(2, 447, 1000000007)时：

• 用long long存中间值u，能得到正确结果941778035
• 换成int存u，结果直接变成0

先看两个版本的函数实现：

正确版本（使用long long） #

int modpow(int x, int n, int m) { //计算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） #

int modpow(int x, int n, int m) { //计算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;
}

错误原因分析 #

在错误版本里，递归计算到某一步时，u的值会接近m（也就是1e9+7），这时候执行u*u就出问题了：

• int类型的取值范围是 -2^31 到 2^31-1（大概-21亿到21亿）
• 1e9+7乘1e9+7的结果是1e18级别的，远远超出int的承载上限，直接触发整数溢出

溢出后，u*u的结果会变成无意义的负数或乱码值，再对m取模自然就得到错误结果（比如例子里的0）。

而正确版本用long long就没这个问题：

• long long是64位整数，取值范围能到 -9e18 到 9e18，完全装得下(1e9+7)*(1e9+7)的结果
• 先完成u*u的计算，再对m取模，最后转成int返回也安全——因为模的结果肯定小于1e9+7，而1e9+7比int的最大值2147483647小，转换不会出问题

验证小技巧 #

你可以在错误版本里加个打印，看看溢出后的真实情况：

int modpow(int x, int n, int m) {
    if (n == 0) return 1%m;
    int u = modpow(x,n/2,m);
    cout << "当前u值: " << u << ", 真实u*u值: " << (long long)u*u << ", 溢出后u*u值: " << u*u << endl;
    u = (u*u)%m;
    if (n%2 == 1) u = (u*x)%m;
    return u;
}

运行后会发现，当u足够大时，u*u的int计算结果已经完全偏离真实值，这就是错误的根源。

内容的提问来源于stack exchange，提问作者VIr