C++ 中最大的回文积
c++server side programmingprogramming
假设输入 n，我们需要找到两个 n 位数字相乘所能得到的最大回文数。由于数字很大，我们可以使用 1337 进行取模运算。因此，如果输入是 2，那么答案就是 987，987 = (99*91) mod 1337 = 9009 mod 1337 = 987。
为了解决这个问题，我们将遵循以下步骤 −
- maxVal := 10^n – 1
- minVal := maxVal / 10
- 初始化 h := maxVal，当 h > 时minVal，更新(将 h 减少 1)，执行 −
- left := h，right := 0
- 初始化 i := h，当 i > 0 时，更新 right = right * 10 + i mod 10，left := left * 10，i := i / 10，执行 −
- x := left + right
- 初始化 i := maxVal，当 i > minVal 时，更新(将 i 减少 1)，执行 −
- 如果 i < x / i，然后减去
- 退出循环
- 如果 x mod i 等于 0，则减去
- 返回 x mod 1337
- 如果 i < x / i，然后减去
- return 9
让我们看看下面的实现以便更好地理解 −
示例
#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
