C++에서 가장 큰 회문 제품

입력 n이 있다고 가정하고 두 n자리 숫자의 곱을 사용하여 만들 수 있는 가장 큰 회문을 찾아야 합니다. 숫자가 매우 크므로 1337을 사용하여 mod를 수행할 수 있습니다. 따라서 입력이 2라고 하면 답은 987, 987 =(99*91) mod 1337 =9009 mod 1337 =987이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 최대값 :=10^n – 1
• 최소값 :=최대값 / 10
• 초기화 h:=maxVal의 경우, h> minVal일 때 업데이트(h를 1만큼 감소), 수행 -
  • 왼쪽 :=h, 오른쪽 :=0
  • 초기화 i :=h의 경우 i> 0일 때 right =right * 10 + i mod 10, left :=left * 10, i :=i / 10, do −
    • x :=왼쪽 + 오른쪽
    • i를 초기화하기 위해:=maxVal, i> minVal일 때 업데이트(i를 1만큼 감소), 수행 -
      • i
      • 루프에서 빠져나오기
    • x mod i가 0과 같으면 -
      • 반환 x 모드 1337

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int largestPalindrome(int n) {
      int maxVal = pow(10, n) - 1;
      int minVal = maxVal / 10;
      for(int h = maxVal; h > minVal; h--){
         lli left = h;
         lli right = 0;
         for(lli i = h; i > 0; right = right * 10 + i % 10, left*= 10, i/= 10);
         lli x = left + right;
         for(int i = maxVal; i > minVal; i--){
            if(i < x / i) break;
            if(x % i == 0) return x % 1337;
         }
      }
      return 9;
   }
};
main(){
   Solution ob;
   cout << (ob.largestPalindrome(3));
}

입력

3

출력

123