Super Palindromes trong C ++

Giả sử chúng ta có một số nguyên dương N, được cho là một số nguyên dương nếu nó là một palindrome, và nó cũng là bình phương của một palindrome. Bây giờ, hãy xem xét chúng ta có hai số nguyên dương L và R, chúng ta phải tìm số siêu chuẩn trong phạm vi bao gồm của [L, R].

Vì vậy, nếu đầu vào giống như L =5 và R =500, thì đầu ra sẽ là 3, siêu chuẩn là 9, 121, 484.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm helper (), điều này sẽ lấy x, m, M, lb, ub,

• nếu x> ub, thì -

  • trở lại

• nếu x> =lb và (x * x) là palindrome thì -

  • (tăng ans lên 1)

• để khởi tạo i:=1, khi m + 2 * i <=M, cập nhật (tăng i lên 1), thực hiện:

  • W:=10 ^ (m + 2 * i - 1)

  • w:=10 ^ i

  • để khởi tạo z:=1, khi z <=9, hãy cập nhật (tăng z lên 1), thực hiện -

    • trình trợ giúp (z * W + x * w, m + 2 * i, M, lb, ub)

• Từ phương thức chính, thực hiện như sau -

• lb:=căn bậc hai của L, ub:=căn bậc hai của R

• M:=thực hiện log của ub cơ số 10 + 1

• để khởi tạo z:=0, khi z <=9, hãy cập nhật (tăng z lên 1), do−

  • trình trợ giúp (z, 1, M, lb, ub)

  • trình trợ giúp (11 * z, 2, M, lb, ub)

• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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"));
}

Đầu vào

"5", "500"

Đầu ra

3