题解 P1218 【[USACO1.5]特殊的质数肋骨 Superprime Rib】
ShineEternal
2019-07-04 10:40:35
# 前言：
简单看了一下其他题解，发现思路~~貌似~~比较独特，没有重复，于是来分析一下。
---
# 分析：
我们首先想到，如果穷举n位的所有数字可能会超时，便不妨设想已经枚举出来，然后观察一下规律。
由题目可以很容易的得出，n位数的特殊质数中最高位一定是质数~~废话~~
这样一位的质数就简单了：2,3,5,7
那么倒推回去，一定只有这些数字开头。
瞬间就爽了很多。
然后再考虑后面的数位。
这时就不能片面的判断单独一位能否影响整个数字了。但我们至少可以得出结论，肋骨一定**不在**以2,4,5,6,8里。
换句话说就可能在1，3,7,9中。
于是一位一位算就行。
我用了两个数组来回倒腾。
**代码长度适中，但仔细一看就会发现很好写**
> code:
```cpp
#include<cstdio>
#include<cmath>
using namespace std;
int ex[5]={0,1,3,7,9},a[100005],b[100005];
bool pd(int x)
{
for(int i=2;i<=sqrt(x);i++)
{
if(x%i==0)return 0;
}
return 1;
}
int main()
{
int n;
scanf("%d",&n);
a[1]=2;
a[2]=3;
a[3]=5;
a[4]=7;
int cnt=4;
int flag=0;
int sum=0;
n--;
while(n--)
{
if(flag==0)
{
sum=0;
for(int i=1;i<=cnt;i++)
{
for(int j=1;j<=4;j++)
{
b[++sum]=a[i]*10+ex[j];
if(!pd(b[sum]))
{
b[sum--]=0;
}
}
}
}
else
{
cnt=0;
for(int i=1;i<=sum;i++)
{
for(int j=1;j<=4;j++)
{
a[++cnt]=b[i]*10+ex[j];
if(!pd(a[cnt]))
{
a[cnt--]=0;
}
}
}
}
flag=(flag+1)%2;
}
if(flag==0)
{
for(int i=1;i<=cnt;i++)
{
printf("%d\n",a[i]);
}
}
else
{
for(int i=1;i<=sum;i++)
{
printf("%d\n",b[i]);
}
}
return 0;
}
```