양의 정수 N이 있다고 가정합니다. 회문은 초회문이라고 하며 회문의 제곱이기도 합니다. 이제 두 개의 양의 정수 L과 R이 있다고 생각하면 [L, R]의 포함 범위에서 초회문(superpalindrome)의 수를 찾아야 합니다.
따라서 입력이 L =5 및 R =500과 같으면 출력은 3이 되고 초회문은 9, 121, 484가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
helper() 함수를 정의합니다. x, m, M, lb, ub,
-
x> ub이면 -
-
반환
-
-
x>=lb이고 (x * x)가 회문이면 -
-
(1만큼 증가)
-
-
i:=1 초기화의 경우, m + 2 * i <=M일 때 업데이트(i를 1만큼 증가), 수행:
-
승 :=10^(m + 2 * i - 1)
-
승 :=10^i
-
초기화 z :=1의 경우 z <=9일 때 업데이트(z를 1만큼 증가), −
-
도우미(z * W + x * w, m + 2 * i, M, lb, ub)
-
-
-
기본 방법에서 다음을 수행하십시오 -
-
lb :=L의 제곱근, ub :=R의 제곱근
-
M :=ub base 10 + 1의 로그 수행
-
초기화 z :=0의 경우, z <=9일 때 업데이트(z를 1만큼 증가), do−
-
도우미(z, 1, M, lb, ub)
-
도우미(11 * z, 2, M, lb, ub)
-
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#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