题目描述循环素数是一个素数当它的最左边数字最高有效位依次移到右边时得到的数仍然是素数。例如数字199371993719937是一个循环素数因为序列199371993719937、993719937199371、937199371993719、371993719937199和719937199371993中的所有数字都是素数。你的目标是编写一个程序给定一个范围计算该范围内循环素数的数量。输入格式输入由一系列整数对iii和jjj组成每行一对整数。所有整数都小于100000010000001000000且大于或等于100100100。可以假设在任何一对中i≤ji \le ji≤j。你应该处理所有整数对对于每一对计算iii和jjj之间包括iii和jjj的循环素数数量。输入由一行仅包含数字-1终止。输出格式对于每一对定义范围的输入整数输出应为No Circular Primes.如果范围内没有循环素数1 Circular Prime.如果范围内只有一个循环素数或n Circular Primes.如果范围内有nnn个循环素数且nnn大于111。样例输入1000 1100 100 120 100 1000 -1样例输出No Circular Primes. 1 Circular Prime. 12 Circular Primes.题目分析本题要求计算给定范围内的循环素数数量。循环素数的定义是一个素数其所有循环移位将最左边的数字移到最右边得到的数都是素数。例如199371993719937的所有循环移位都是素数因此它是循环素数。需要注意循环素数的所有循环移位必须具有相同的位数因此不能有前导零。这意味着如果数字中包含000则循环移位后可能出现前导零导致位数减少这样的数字通常不是循环素数除非移位后的数仍然是素数且位数不变但实际上前导零会使得数值变小且位数减少通常不会保持素数性质但严格来说需要检查移位后的数值是否为素数而不是字符串是否保持位数。例如数字101101101循环移位得到01111011 1101111111111是素数但101101101本身是素数所以101101101是循环素数吗根据定义101101101的循环移位是011011011即111111111111是素数所以101101101应该是循环素数。然而在本题的代码实现中通过计算nextNumber的方式实际上会正确处理前导零的情况因为数值计算会自然去掉前导零。但需要注意的是如果原始数字包含000循环移位后得到的数值可能位数减少这仍然是允许的只要得到的数值是素数即可。不过通常循环素数的定义要求所有循环移位都是素数不要求位数相同但要求数值本身是素数。本题的代码实现通过数值计算来处理循环移位因此可以正确处理包含000的情况。代码首先使用线性筛法欧拉筛生成所有小于100001010000101000010的素数并存储在数组primes中。然后遍历每个素数检查它是否为循环素数。对于每个素数通过循环移位生成所有可能的数并使用二分查找检查生成的数是否在素数数组中。如果所有循环移位都是素数则将该素数加入circular数组。最后构建前缀和数组range其中range[i]表示小于等于iii的循环素数数量。对于每个查询范围[start,end][start, end][start,end]通过range[end] - range[start - 1]快速得到答案并根据数量输出相应的格式。循环移位的计算对于数字nnn取出最低位nextNumber n % 10然后计算剩余部分n / 10的位数将nextNumber乘以相应的101010的幂再加上n / 10得到循环移位后的数字。例如199371993719937最低位是777剩余部分199319931993有444位所以7×100001993719937 \times 10000 1993 719937×10000199371993。重复这个过程直到回到原始数字。时间复杂度筛法O(MAXN)O(MAXN)O(MAXN)检查循环素数O(π(MAXN)×L)O(\pi(MAXN) \times L)O(π(MAXN)×L)其中π(MAXN)\pi(MAXN)π(MAXN)是素数个数LLL是数字位数最多666位构建前缀和O(MAXN)O(MAXN)O(MAXN)查询O(1)O(1)O(1)。总时间复杂度可以接受。空间复杂度O(MAXN)O(MAXN)O(MAXN)。解题思路使用欧拉筛法预处理出所有小于100001010000101000010的素数存储在primes数组中。然后遍历每个素数对于每个素数通过循环移位生成所有可能的数并检查它们是否都是素数。如果是则将该素数记录为循环素数。最后构建前缀和数组以便快速回答范围查询。循环移位的具体实现对于数字nnn初始化originalNumber n然后循环执行以下操作取出最低位nextNumber originalNumber % 10计算剩余部分的位数将nextNumber乘以对应的101010的幂再加上originalNumber / 10得到新的数字。如果新数字不在素数集合中则标记为不是循环素数并跳出。重复直到新数字等于原始数字nnn。如果所有循环移位都是素数则nnn是循环素数。注意在检查循环移位时使用二分查找在有序的primes数组中查找因为primes数组是按升序排列的。这样可以快速判断一个数是否为素数。代码实现// Circular// UVa ID: 967// Verdict: Accepted// Submission Date: 2017-03-08// UVa Run Time: 0.050s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intMAXN1000010,primes[MAXN],primeCounter0;memset(primes,0,sizeof(primes));for(inti2;iMAXN;i){if(!primes[i])primes[primeCounter]i;for(intj0;jprimeCounteri*primes[j]MAXN;j){primes[i*primes[j]]-1;if(!(i%primes[j]))break;}}intcircular[10000],circularCounter0,remainder[6]{10,100,1000,10000,100000,1000000};for(intk0;kprimeCounter;k){boolisCirculartrue;intoriginalNumberprimes[k],nextNumber,idx;do{idx0;nextNumberoriginalNumber%10;while(originalNumberremainder[idx]){nextNumber*10;idx;}nextNumberoriginalNumber/10;originalNumbernextNumber;isCircularbinary_search(primes,primesprimeCounter,nextNumber);if(!isCircular)break;}while(nextNumber!primes[k]);if(isCircular)circular[circularCounter]primes[k];}intrange[MAXN];for(inti0,j0;iMAXN;i){range[i]0;if(icircular[j]){range[i]1;j;}range[i]range[i-1];}intstart,end;while(cinstart,start0){cinend;intrangeCounterrange[end]-range[start-1];if(rangeCounter0)coutNo Circular Primes.\n;elseif(rangeCounter1)cout1 Circular Prime.\n;elsecoutrangeCounter Circular Primes.\n;}return0;}总结本题的关键在于高效地判断循环素数并快速回答范围查询。通过欧拉筛法预处理素数然后对每个素数检查其所有循环移位是否都是素数。循环移位的计算通过数值操作完成避免了字符串转换的开销。使用二分查找在有序素数数组中快速判断一个数是否为素数。最后通过前缀和数组实现O(1)O(1)O(1)的范围查询。整体算法在给定数据规模下运行效率高时间复杂度约为O(MAXNπ(MAXN)×L)O(MAXN \pi(MAXN) \times L)O(MAXNπ(MAXN)×L)空间复杂度为O(MAXN)O(MAXN)O(MAXN)。注意处理输入终止条件-1以及输出格式的复数形式。