Project Euler #206暴力范围枚举算法输出错误答案问题求解

我正在解决Hackerrank竞赛题集中的Project Euler第206题，题目要求为：找到唯一的正整数，其平方的十进制表示符合给定的间隔位模式：模式中部分位为已知固定数字，剩余位为未知单个数字，已知位从首位开始、包含末位间隔排列。

优化前的暴力解法思路如下：

• 输入模式示例为8_7_6（_代表未知数字），先计算x的取值范围：将模式的未知位分别替换为0和9，得到最小可能值80706和最大可能值89796，x的范围为[ceil(sqrt(80706)), floor(sqrt(89796))]即[284, 299]
• 遍历范围内所有整数，计算平方后校验是否符合输入模式，示例中遍历得到286² = 81796符合要求
• 后续可通过平方数末位性质剪枝：如示例中平方末位为6，x的末位只能是4或6，仅需校验{284, 286, 294, 296}即可减少遍历次数

算法已通过前8个测试用例，但部分测试用例被判输出错误，超时属于未优化的正常现象，需要定位错误答案的产生原因。

• 整数溢出问题：当输入模式较长时，对应平方值和x的数值会超过32位整数的存储上限（最大约2e9），如果使用int等32位类型存储计算结果，会发生溢出截断导致平方值计算错误，建议改用long long等64位整数类型或大整数类处理运算。
• 范围取整错误：通过浮点数sqrt计算上下界时，可能因为浮点数精度丢失导致取整错误，比如较大的整数开平方后浮点数无法精确表示，向下取整时少1或者向上取整时多1，建议计算完上下界后额外校验边界值的平方是否落在合法区间内。
• 模式匹配逻辑错误：校验平方值和模式匹配时，容易出现数位对应错误：比如将平方值的数位从右往左计数，和从左往右排列的模式位对应错位，或者没有先补前导零保证平方值的位数和模式长度完全一致，导致已知位匹配错误。
• 剪枝逻辑错误：如果使用了末位剪枝优化，要确认平方末位和x末位的对应关系是否正确，比如平方末位为0时x末位只能是0，平方末位为2/3/7/8时没有合法解，规则写错会直接漏掉正确的x值。

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