0479. Largest Palindrome Product ================================ 题目信息 -------- :题号: 0479 :难度: Hard :主题: ``n`` 位整数、两数乘积、最大回文数、模 1337 :原题: `LeetCode 0479 `_ :重点: 两个因数都必须恰好是 ``n`` 位正整数、先找最大回文乘积、最后才对 1337 取模 题目重述 -------- 给定整数 ``n``,在所有两个 ``n`` 位正整数的乘积中,找出数值最大的回文数,并返回该回文数对 ``1337`` 取模后的结果。 回文数的十进制表示从左向右和从右向左完全相同。两个因数都必须位于 ``[10^(n-1), 10^n-1]``;返回值不是最大回文数本身,而是其余数。``n`` 位于 ``[1, 8]``,题目保证所需最大回文乘积存在。 自建示例 -------- 一位数因数: .. code-block:: text 输入:n = 1 输出:9 解释:由两个一位正整数相乘能够得到的最大回文数是 9,例如 9 × 1 = 9;9 对 1337 取模仍为 9。 取模发生在确定最大值之后: .. code-block:: text 输入:任意合法 n 输出:largestPalindrome mod 1337 解释:不能比较各乘积取模后的大小来选择答案,必须先比较原始乘积并确定最大的回文数。 从最大半段生成回文并利用 11 的因子 ---------------------------------- 对 ``n > 1``,最大回文乘积可以按偶数位回文的形式搜索:取一个 ``n`` 位的左半段 ``half``,拼接它的逆序得到完整回文。按 ``half`` 从大到小生成,就已经按回文数值从大到小检查。 偶数位回文数能被 11 整除,因此两个因数中至少有一个是 11 的倍数。内层只枚举从最大 ``n`` 位数向下的 11 的倍数,并在“该因数乘最大因数都已小于当前回文”时停止;找到处于合法位数范围的整除关系后,立即对原始回文取模。``n = 1`` 单独处理,因为最大的结果是 ``9`` 而不是两位回文。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int largestPalindrome(int n) { if (n == 1) return 9; long long lower = 1; for (int i = 1; i < n; ++i) lower *= 10; long long upper = lower * 10 - 1; long long factorStart = upper - upper % 11; for (long long half = upper; half >= lower; --half) { std::string left = std::to_string(half); std::string right = left; std::reverse(right.begin(), right.end()); long long palindrome = std::stoll(left + right); for (long long factor = factorStart; factor >= lower; factor -= 11) { if (factor * upper < palindrome) break; if (palindrome % factor != 0) continue; long long other = palindrome / factor; if (other >= lower && other <= upper) { return static_cast(palindrome % 1337); } } } return 0; } }; 代码分析 -------- 半段按降序生成保证第一次找到的就是原始值最大的可行回文;11 的因子性质把因数搜索缩小到约每 11 个数取一个,乘积上界剪枝又排除了不可能达到当前回文的因数。使用 ``long long`` 可容纳 ``n <= 8`` 时的最多 16 位乘积,取模只在确定最大回文后进行;额外空间复杂度为 ``O(n)``,时间取决于实际检查的半段和候选因数数量。