C++で最大のパリンドローム製品

nを入力したとすると、2つのn桁の数値の乗算を使用して作成できる最大の回文を見つける必要があります。数値が非常に大きいため、1337を使用してmodを実行できます。したがって、入力が2の場合、答えは987、987 =（99 * 91）mod 1337 =9009 mod 1337=987になります。

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

• maxVal：=10 ^ n – 1
• minVal：=maxVal / 10
• hを初期化する場合：=maxVal、h> minValの場合、更新（hを1つ減らす）、実行-
  • 左：=h、右：=0
  • 初期化i：=hの場合、i> 0の場合、右=右* 10 + i mod 10、左：=左* 10、i：=i / 10、do −
    を更新します。
    • x：=左+右
    • iを初期化する場合：=maxVal、i> minValの場合、更新（iを1つ減らす）、実行-
      • i
      • ループから抜け出す
    • x mod iが0と同じ場合、-
      • return x mod 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