奇怪的数字

Question

以下是我正在做的问题中"奇怪数字"的属性:

1)它们具有偶数个十进制数字(无前导零).

2)将左半部分定义为原始数字的最重要的一半数字所代表的数字,将右半部分定义为最不重要的一半代表的数字.右半部分可能有前导零.奇怪的数字是它的一半之和的平方:81 =(8 + 1)^ 2

以下是一些其他示例:998001 =(998 + 001)^ 2,2025 =(30 + 25)^ 2

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

我通过查看所有可能性(2位数,4位数,6位数,......,18位数)来了解如何执行此操作,但这需要数天才能运行.有没有任何模式,所以我可以在几秒钟内输出所有奇怪的数字？我更喜欢Java中的答案,但伪代码也没关系.

Answer 1

所有这些"奇怪"的数字都是完美的正方形.因此,您可以先浏览所有数字并将它们平方(直到正方形超过18位).对于每个广场,检查它是否"奇怪".

编辑 我还要补充说,这个速度增加的原因是它将解决方案从O(n)改为O(√n)