NC25190. 完美手链
描述
三玖快要过生日了，作为一个直男，zjq 打算自己 diy 一条手链送给三玖，这条手链是与众不同的，它有以下特征：
1. 手链由 1~7 个珠子串成；
2. 手链的每个珠子上都有一个 0~9 的数字；
3. 从每个珠子出发，把手链珠子上的数字顺时针连在一起，都能得到一个素数。
比如有一个手链的珠子上的数字依次为 1、9、9、3、7，那么从每个珠子开始顺时针数一圈分别可以得到 19937，99371，93719，37199 和 71993，它们都是素数。
zjq 觉得这样的手链才是完美的手链，但众所周知他的数学不太好，他现在串好了一些手链，请你告诉他它们是不是完美的手链。
输入描述
第一行为一个整数T，T≤1000000，表示数据的组数。
接下来每一行为一个整数P，P＜10000000，P是从手链上某一个珠子开始将数字顺时针连在一起后得到的数字。
输出描述
如果这是一条完美的手链，请输出"Perfect!"，否则请输出"Imperfect."。
示例1
输入:
3 1 2 19937
输出:
Imperfect. Perfect! Perfect!
C++14(g++5.4) 解法, 执行用时: 190ms, 内存消耗: 11104K, 提交时间: 2019-04-21 12:18:46
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int z[100]={2,3,5,7,11,13,17,31,37,71,73,79,97,113,131,197,199,311,337,373,719,733,919,971,991,1193,1931,3119,3779,7793,7937,9311,9377,11939,19391,19937,37199,39119,71993,91193,93719,93911,99371,193939,199933,319993,331999,391939,393919,919393,933199,939193,939391,993319,999331};
int w,e;
int main()
{
int a,s,d;
scanf("%d",&a);
while(a--)
{
scanf("%d",&s);
d=1;
for(int i=0;i<55;i++)
{
if(s==z[i])
{
printf("Perfect!\n");
d=0;
break;
}
}
if(d)
printf("Imperfect.\n");
}
}
C++11(clang++ 3.9) 解法, 执行用时: 646ms, 内存消耗: 17784K, 提交时间: 2019-04-26 18:52:06
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T,p,flag,i,len,j,t,k;
char s[8];
scanf("%d",&T);
while(T--)
{
flag=0;
scanf("%s",s);
len=strlen(s);
for(i=0;i<len;i++)
{
t=0;
for(j=i;j<len+i;j++)
{
t=t*10+(s[j%len]-'0');
}
if(t==2)
{
i=len-1;
}
for(k=2;k<=sqrt(t);k++)
{
if(t%k==0)
{
flag=1;
break;
}
}
if(flag==1||t==0||t==1)
break;
}
if(i==len)
printf("Perfect!\n");
else
printf("Imperfect.\n");
}
}