为什么C++查找n位可被t整除整数的代码在n较大时运行异常

错误原因 #

• 第一个错误：pow函数返回值为double类型，双精度浮点数的有效位数仅为53位二进制（约15~17位十进制），当计算的数值大于2^53（约9e15）时，无法精确表示所有整数，转换为unsigned long long时会出现精度丢失。
• 第二个致命错误：print函数的返回值类型为int，32位int的最大值仅为2^31-1=2147483647（约2e9），当返回的18位整数存入int类型变量时会发生溢出截断，你看到的10位错误值就是溢出截断后的结果。
• 第三个可优化点：不需要从最小值开始遍历找第一个可被t整除的数，直接通过数学计算即可得到结果，避免无意义的循环开销。

修复代码 #

#include<iostream>
using namespace std;

// 实现整数版10^n计算，避免pow的浮点数精度问题
unsigned long long power10(int exp) {
    unsigned long long res = 1;
    for(int i = 0; i < exp; i++) {
        res *= 10;
    }
    return res;
}

// 返回值类型修改为unsigned long long，避免溢出
unsigned long long find(int n, int t) {
    unsigned long long min_val = power10(n - 1);
    // 直接计算第一个符合要求的数值
    unsigned long long mod = min_val % t;
    if(mod == 0) {
        return min_val;
    }
    return min_val + (t - mod);
}

int main() {
    int n, t;
    cin >> n >> t;
    cout << find(n, t);
    return 0;
}

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