C ++中的超级回文

假设我们有一个正整数N，如果它是回文，则被称为超级回文，并且它也是回文的平方。现在考虑我们有两个正整数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），请执行以下操作：

• 助手（z * W + x * w，m + 2 * i，M，lb，ub）

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

• w：= 10 ^ i

• 对于初始化z：= 1，当z <= 9时，更新（将z增加1），执行-

• 从主要方法中，执行以下操作-

• lb：= L的平方根，ub：= R的平方根

• M：=执行ub base 10 + 1的日志

• 对于初始化z：= 0，当z <= 9时，更新（将z增加1），执行-

• 助手(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