題目網址：C - Fair and Square

題目概述

題目要求找出給定的區間 [A,B] 中，有幾個回文其平方根也是回文。例如：1、9、121 都符合條件，因為其平方根為 1、3、11 也都為回文。我決定接下來都姑且稱呼該種回文為「平方回文」。

Technique Detail

small case

• 1 ≤ T ≤ 100
• 1 ≤ A ≤ B ≤ 1000

large case 1

• 1 ≤ T ≤ 10000
• 1 ≤ A ≤ B ≤ 10¹⁴

large case 2

• 1 ≤ T ≤ 1000
• 1 ≤ A ≤ B ≤ 10¹⁰⁰

輸入格式

測試資料由一個整數 T 開始，表示接下來會有 T 比測試資料。而每筆測試資料都僅包含兩個整數 A 與 B，表示所要求的區間。

輸出格式

輸出給定的區間 [A,B] 中有幾個符合題目所要求的回文。

---

解題思路

針對 small case，我直接採用暴力法解決。但很蠢的我以為 large case 1 也可以，就嘗試了暴力法，不僅拿到了 time expired，還搞的電腦記憶體耗盡當機了只能強迫關機…。

後來決定採用建表的方式，直接將題目要求的範圍內的平方回文找出來，再從表中篩選出有幾個回文是位於區間 [A,B] 之中。很明顯地，關鍵就是如何快速的建表。

先從一位數開始，枚舉 1-9 之中，哪些是回文而且其平方後的值也是回文。如果找到的話，就將該回文丟進一個 seed set 中，並將平方後的回文丟進表中。

接著把 0 也丟進 seed set 中，接下來枚舉 seed set 中的回文，並從依照 1-9 的順序將數字加在其兩邊以形成一個新的回文，新的回文在做平方，看齊平方後的值是否為回文。如果是的話就把該回文再丟進一個新的 seed set，並將平方後的回文丟進表中。如果平方後的值不是回文，那麼就終止這個在兩邊加上數字的循環。也就是說假設加入 2 時，平方後的值仍是回文，那麼就繼續嘗試加入 3 的情況。而加入 3 的時候，平方後的值不為回文，那麼就可以停止了不需要再嘗試加入 4 的情況。可以這麼做的原因在於，要讓平方後的直為回文的話，那麼運算過程中，不該有進位的情況發生。如果加入 3 就發生了進位，那麼加入 4 也會發生，所以也不需要再考慮了！

枚舉完後再把 000 丟入新的 seed 中，再用相同的方式找出新的 seed set 以及平方回文。依照當前枚舉的回文位數，都要再將相同位數的 0 丟入新的 seed set 中，如此重複運算就可以找出所有的平方回文了！

對於偶數位的回文也是採用相同的方式，先枚舉 11、22、…，並將 seed set 用相同的方式處理即可。

至於什麼時候停止呢？我原本是看題目的範圍是多少就定多少，例如 large case 2 的最大值為 10¹⁰⁰，我就定在當枚舉的位數超過 100 時就停止。也因為這樣，我在跑 large case 2 時，竟然差點超過 8 分鐘，還好在最後 10 秒內程式有跑完，才不至於拿到第二個 time expired！但其實枚舉的量只需要到 50 位即可，由於我枚舉的是開平方根後的數值，該數值平方後位數就會成長近一倍！所以要找到 10¹⁰⁰ 的平方回文，只需要枚舉到 10⁵⁰ 即可。

最後在針對每一筆測資於表中搜尋位於 [A,B] 的回文有幾個即可。

Source Code

Source code on gist.