奇怪的数字

Question

以下是我正在做的问题中“奇怪数字”的属性：

1）它们的偶数个小数位（无前导零）。

2）将左半部分定义为原始数字的最高有效半数所代表的数字，右半部分代表最低有效半数所代表的数字。右半部分可能有前导零。奇数是它的一半的平方和：81 =（8 + 1）^ 2

这里是一些其他例子：998001 =（998 + 001）^ 2，3025 =（30 + 25）^ 2

如何编写一个程序，该程序按递增顺序列出所有不超过18位十进制数的奇怪数字？

我明白如何通过查看所有可能性（2位数字，4位数字，6位数字，...，18位数字）来完成此操作，但这需要几天时间才能运行。是否有任何模式，所以我可以在几秒钟内输出所有奇怪的数字？我更喜欢Java中的答案，但伪代码也可以。

Answer 1

所有这些'奇怪'的数字是完美的正方形。因此，您可以先浏览所有数字并将其平方（直到广场的数字超过18位）。对于每个广场，检查一下是否“奇怪”。

编辑 我还要补充一点，之所以这个速度的东西了这么多的是，它改变了从O（N）至O解决方案（√ N）

Answer 2

除了@ spatulamania的加速，您可以使用模运算来进一步加速检查。

要检查每个完美的正方形，您必须将数字拆分为两部分，添加它们，将总和平方并将其与原始数字进行比较。 （我将它命名为“全面检查”）

相反，您可以只检查两部分的最后几位（并将它们的总和平方）。例如，对于编号为99980001的数字，请采用8和1的数字，取(8+1)^2 = 9^2 = 81的平方，并测试最后一位数字（本例中为1）与最后一位数字99980001相同（我将其命名为“small-check “）。如果是，则继续进行全面检查。

由于只有10x10 = 100个这样的组合，这只需要做一次。您将创建可接受组合的数组，你可以使用：

0 0 
0 1 
8 1 
4 4 
8 4 
0 5 
0 6 
8 6 
4 9 
8 9 

利用这一点，你只需要做到“小勾选”完美的正方形的约82％（那些失败小额支票），并检查其余18％（通过小支票，所以“全面支票”也将需要）。因此，如果“小检查”可以做得足够快，你会获得一些速度。

您可能会发现甚至更快地将这个表扩展为两个部分的最后2位数并使用它（当n足够大时）。