题目描述

循环素数是一个素数，当它的最左边数字（最高有效位）依次移到右边时，得到的数仍然是素数。例如，数字 $19937$ 是一个循环素数，因为序列 $19937$、$99371$、$93719$、$37199$ 和 $71993$ 中的所有数字都是素数。你的目标是编写一个程序，给定一个范围，计算该范围内循环素数的数量。

输入格式

输入由一系列整数对 $i$ 和 $j$ 组成，每行一对整数。所有整数都小于 $1000000$ 且大于或等于 $100$。可以假设在任何一对中 $i\le j$。你应该处理所有整数对，对于每一对，计算 $i$ 和 $j$ 之间（包括 $i$ 和 $j$）的循环素数数量。输入由一行仅包含数字 -1 终止。

输出格式

对于每一对定义范围的输入整数，输出应为：No Circular Primes.（如果范围内没有循环素数），1 Circular Prime.（如果范围内只有一个循环素数），或 n Circular Primes.（如果范围内有 $n$ 个循环素数，且 $n$ 大于 $1$）。

样例输入

1000 1100
100 120
100 1000
-1

样例输出

No Circular Primes.
1 Circular Prime.
12 Circular Primes.

题目分析

本题要求计算给定范围内的循环素数数量。循环素数的定义是：一个素数，其所有循环移位（将最左边的数字移到最右边）得到的数都是素数。例如 $19937$ 的所有循环移位都是素数，因此它是循环素数。需要注意，循环素数的所有循环移位必须具有相同的位数，因此不能有前导零。这意味着如果数字中包含 $0$，则循环移位后可能出现前导零，导致位数减少，这样的数字通常不是循环素数（除非移位后的数仍然是素数且位数不变，但实际上前导零会使得数值变小且位数减少，通常不会保持素数性质，但严格来说需要检查移位后的数值是否为素数，而不是字符串是否保持位数。例如数字 $101$，循环移位得到 $011=11$，$11$ 是素数，但 $101$ 本身是素数，所以 $101$ 是循环素数吗？根据定义，$101$ 的循环移位是 $011$ 即 $11$，$11$ 是素数，所以 $101$ 应该是循环素数。然而，在本题的代码实现中，通过计算 nextNumber 的方式，实际上会正确处理前导零的情况，因为数值计算会自然去掉前导零。但需要注意的是，如果原始数字包含 $0$，循环移位后得到的数值可能位数减少，这仍然是允许的，只要得到的数值是素数即可。不过，通常循环素数的定义要求所有循环移位都是素数，不要求位数相同，但要求数值本身是素数。本题的代码实现通过数值计算来处理循环移位，因此可以正确处理包含 $0$ 的情况。

代码首先使用线性筛法（欧拉筛）生成所有小于 $1000010$ 的素数，并存储在数组 primes 中。然后遍历每个素数，检查它是否为循环素数。对于每个素数，通过循环移位生成所有可能的数，并使用二分查找检查生成的数是否在素数数组中。如果所有循环移位都是素数，则将该素数加入 circular 数组。最后，构建前缀和数组 range，其中 range[i] 表示小于等于 $i$ 的循环素数数量。对于每个查询范围 $[start,end]$，通过 range[end] - range[start - 1] 快速得到答案，并根据数量输出相应的格式。

循环移位的计算：对于数字 $n$，取出最低位 nextNumber = n % 10，然后计算剩余部分 n / 10 的位数，将 nextNumber 乘以相应的 $10$ 的幂，再加上 n / 10，得到循环移位后的数字。例如 $19937$，最低位是 $7$，剩余部分 $1993$ 有 $4$ 位，所以 $7\times 10000+1993=71993$。重复这个过程直到回到原始数字。

时间复杂度：筛法 $O(MAXN)$，检查循环素数 $O(\pi (MAXN)\times L)$，其中 $\pi (MAXN)$ 是素数个数，$L$ 是数字位数（最多 $6$ 位），构建前缀和 $O(MAXN)$，查询 $O(1)$。总时间复杂度可以接受。空间复杂度 $O(MAXN)$。

解题思路

使用欧拉筛法预处理出所有小于 $1000010$ 的素数，存储在 primes 数组中。然后遍历每个素数，对于每个素数，通过循环移位生成所有可能的数，并检查它们是否都是素数。如果是，则将该素数记录为循环素数。最后构建前缀和数组，以便快速回答范围查询。

循环移位的具体实现：对于数字 $n$，初始化 originalNumber = n，然后循环执行以下操作：取出最低位 nextNumber = originalNumber % 10，计算剩余部分的位数，将 nextNumber 乘以对应的 $10$ 的幂，再加上 originalNumber / 10，得到新的数字。如果新数字不在素数集合中，则标记为不是循环素数并跳出。重复直到新数字等于原始数字 $n$。如果所有循环移位都是素数，则 $n$ 是循环素数。

注意：在检查循环移位时，使用二分查找在有序的 primes 数组中查找，因为 primes 数组是按升序排列的。这样可以快速判断一个数是否为素数。

代码实现

// Circular
// UVa ID: 967
// Verdict: Accepted
// Submission Date: 2017-03-08
// UVa Run Time: 0.050s
//
// 版权所有（C）2017，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[])
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

    int MAXN = 1000010, primes[MAXN], primeCounter = 0;

    memset(primes, 0, sizeof(primes));

    for (int i = 2; i < MAXN; i++)
    {
        if (!primes[i]) primes[primeCounter++] = i;
        for (int j = 0; j < primeCounter && i * primes[j] < MAXN; j++)
        {
            primes[i * primes[j]] = -1;
            if (!(i % primes[j])) break;
        }
    }

    int circular[10000], circularCounter = 0, remainder[6] = {10, 100, 1000, 10000, 100000, 1000000};
    for (int k = 0; k < primeCounter; k++)
    {
        bool isCircular = true;
        int originalNumber = primes[k], nextNumber, idx;
        do
        {
            idx = 0;
            nextNumber = originalNumber % 10;
            
            while (originalNumber > remainder[idx])
            {
                nextNumber *= 10;
                idx++;
            }

            nextNumber += originalNumber / 10;
            originalNumber = nextNumber;

            isCircular = binary_search(primes, primes + primeCounter, nextNumber);
            if (!isCircular) break;

        } while (nextNumber != primes[k]);

        if (isCircular) circular[circularCounter++] = primes[k];
    }
    
    int range[MAXN];
    for (int i = 0, j = 0; i < MAXN; i++)
    {
        range[i] = 0;
        if (i == circular[j])
        {
            range[i] = 1;
            j++;
        }
        range[i] += range[i - 1];
    }
    
    int start, end;
    while (cin >> start, start > 0)
    {
        cin >> end;
        int rangeCounter = range[end] - range[start - 1];
        if (rangeCounter == 0) cout << "No Circular Primes.\n";
        else if (rangeCounter == 1) cout << "1 Circular Prime.\n";
        else cout << rangeCounter << " Circular Primes.\n";
    }

    return 0;
}

总结

本题的关键在于高效地判断循环素数并快速回答范围查询。通过欧拉筛法预处理素数，然后对每个素数检查其所有循环移位是否都是素数。循环移位的计算通过数值操作完成，避免了字符串转换的开销。使用二分查找在有序素数数组中快速判断一个数是否为素数。最后，通过前缀和数组实现 $O(1)$ 的范围查询。整体算法在给定数据规模下运行效率高，时间复杂度约为 $O(MAXN+\pi (MAXN)\times L)$，空间复杂度为 $O(MAXN)$。注意处理输入终止条件 -1，以及输出格式的复数形式。