奇怪的數字

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足夠大時）。