洛谷：P1217：回文质数

题目

P1217：回文质数

分析

这道题目不需要太复杂的思路——比如去构造回文数——而可以直接暴力求解。但是，如果一点优化都不进行，在运行最后一个测试用例时会TLE。

首先，我们需要想清楚的是，先要判断是否回文数，这样可以筛掉好多好多数字，然后对回文数再判断是否质数。

回文数判定

回文数判定可以通过字符串操作来实现。对于一个回文数来说，一头/一尾两个数字相等，然后头指针向右、尾指针向左移动一位，继续相等；以此类推，直到头指针的位置大于等于尾指针的位置。¹

bool isPalindrome(int n)
{
    string s = to_string(n);
    int l = 0, r = s.length() - 1;
    while (l < r)
    {
        if (s[l] != s[r])
        {
            return false;
        }
        l++;
        r--;
    }
    return true;
}

至于是否是素数的判定，这里不重复。

回文素数的一个重要特性

题目中给出的数字范围很大（b可以取值到\(10^8\)），如果真的用最朴素的暴力算法，那么会超时。

这里需要一个洞见：如果一个回文数是2/4/6/8……等偶数位的，那么一定不会是素数（除了11）。所以，如果我们在循环中跳过这些数，就会大大节省时间，而完成最后一个b=100'000'000的测试用例。

答案

思考

对于上文的结论：如果一个回文数是2/4/6/8……等偶数位的，那么一定不会是素数（除了11）。如何严格证明？

首先，一个数如何能被11整除，那么它的奇数位数字的和与偶数位数字的和的差，一定是可以整除11的。

观察一下一个偶数位数的回文数的组成，一定是形如：\(a_1a_2a_3...a_ka_k...a_3a_2a_1\)。两个对应的数字的位置，形成了第i位和2k-i-1位的关系。而这个关系中的两个位置，一定是一个在奇数位，一个在偶数位。所以，这个数的偶数位数字加起来，一定等于奇数位数字加起来。其差为0，也就一定是11的倍数。