C++のスーパーパリンドローム

正の整数Nがあるとします。これは、回文の場合はスーパーパリンドロームと呼ばれ、回文の2乗でもあります。ここで、2つの正の整数LとRがあると考えて、[L、R]の包括的範囲内のスーパーパリンドロームの数を見つける必要があります。

したがって、入力がL=5およびR=500のような場合、出力は3になり、スーパーパリンドロームは9、121、484になります。

これを解決するには、次の手順に従います-

• 関数helper（）を定義します。これには、x、m、M、lb、ub、

  が必要です。

• x> ubの場合、-

  • 戻る

• x> =lbであり、（x * x）が回文である場合、-

  • （ansを1増やします）

• 初期化i：=1の場合、m + 2 * i <=Mの場合、更新（iを1増やします）、次のようにします。

  • W：=10 ^（m + 2 * i-1）

  • w：=10 ^ i

  • zを初期化する場合：=1、z <=9の場合、更新（zを1つ増やす）、実行-

    • helper（z * W + x * w、m + 2 * i、M、lb、ub）

• メインの方法から、次のようにします-

• lb：=Lの平方根、ub：=Rの平方根

• M：=ubベース10+1のログを実行

• 初期化z：=0の場合、z <=9の場合、更新（zを1増やします）、do-

  • helper（z、1、M、lb、ub）

  • ヘルパー（11 * z、2、M、lb、ub）

• ansを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   int ans = 0;
   public:
   int superpalindromesInRange(string L, string R){
      long double lb = sqrtl(stol(L)), ub = sqrtl(stol(R));
      int M = log10l(ub) + 1;
      for (int z = 0; z <= 9; z++) {
         helper(z, 1, M, lb, ub);
         helper(11 * z, 2, M, lb, ub);
      }
      return ans;
   }
   private:
   void helper(long x, int m, int M, long double lb, long double ub){
      if (x > ub)
      return;
      if (x >= lb && is_palindrome(x * x))
      ans++;
      for (int i = 1; m + 2 * i <= M; i++) {
         long W = powl(10, m + 2 * i - 1) + 1;
         long w = powl(10, i);
         for (int z = 1; z <= 9; z++)
         helper(z * W + x * w, m + 2 * i, M, lb, ub);
      }
   }
   bool is_palindrome(long x){
      if (x == 0)
      return true;
      if (x % 10 == 0)
      return false;
      long left = x, right = 0;
      while (left >= right) {
         if (left == right || left / 10 == right)
         return true;
         right = 10 * right + (left % 10), left /= 10;
      }
      return false;
   }
};
main(){
   Solution ob;
   cout << (ob.superpalindromesInRange("5", "500"));
}

入力

"5", "500"

出力

3