C++实现1-99999区间卡普雷卡数遗漏问题求助

问题描述 #

用C++打印1到99999区间内的所有卡普雷卡数，预期输出包含21个数字：1 9 45 55 99 297 703 999 2223 2728 4950 5050 7272 7777 9999 17344 22222 77778 82656 95121 99999，但实际输出仅得到前17个，遗漏了77778、82656、95121、99999这4个数字。

原代码如下：

#include <bits/stdc++.h>
#include <cmath>

using std::cout;
using std::cin;
using std::endl;
using std::pow;

int b = 0, a = 0;

int main(int argc, char** argv) {
    
    int lower, upper, count = 0;
    cin >> lower >> upper;
    
    for (int i = lower; i <= upper; i++) {
        
        int n = i, digits = 0;
        while (n != 0) {
            digits++;
            n /= 10;
        }
        n = pow(i, 2);
        digits = pow(10, digits);
        b = n % digits;
        a = (n - b) / digits;
        if (a + b == i) {
            cout << i << " ";
            count++;
        }
        digits = 0;
        a = 0;
        b = 0;
    }
    
    if (count == 0) cout << "INVALID RANGE";
    return 0; 
}

问题原因 #

1. pow函数的精度误差：pow是浮点数运算函数，计算大数平方（比如99999的平方是9999800001）或10的高次幂（比如10^5）时，浮点数无法精确表示整数，转成int后会出现截断错误。例如pow(10,5)可能得到99999.99999999999，转int后变成99999，而非预期的100000，导致拆分逻辑出错。
2. int类型溢出：int的取值范围通常是-2147483648到2147483647，而99999的平方是9999800001，远超出这个范围，会导致int溢出，数值变成乱码，后续的拆分计算完全失效。

解决方法 #

• 替换pow函数：用整数运算替代浮点数pow，平方直接用(long long)i * i，10的digits次方用整数循环累乘，避免精度问题。
• 改用更大的数据类型：用long long存储平方结果，彻底避免大数溢出。
• 移除全局变量：原代码中的全局变量a、b完全可以放在循环内，减少不必要的全局状态干扰。

修正后的代码 #

#include <iostream>
using std::cout;
using std::cin;
using std::endl;

int main() {
    int lower, upper, count = 0;
    cin >> lower >> upper;

    for (int i = lower; i <= upper; ++i) {
        // 计算数字的位数
        int n = i;
        int digits = 0;
        while (n != 0) {
            digits++;
            n /= 10;
        }
        if (digits == 0) continue; // 处理i=0的特殊情况，本题区间从1开始可忽略

        // 计算平方，用long long避免溢出
        long long square = (long long)i * i;
        // 计算10^digits，整数累乘替代pow
        long long divisor = 1;
        for (int j = 0; j < digits; ++j) {
            divisor *= 10;
        }

        long long b = square % divisor;
        long long a = square / divisor;
        if (a + b == i) {
            cout << i << " ";
            count++;
        }
    }

    if (count == 0) {
        cout << "INVALID RANGE";
    }
    cout << endl;
    return 0;
}

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