2022summer16
#include<bits/stdc++.h>
using namespace std;
bool is_prime(int x)//判断质数
{
for(int i=2;i*i<=x;i++) if(x%i==0) return 0;
return 1;
}
bool is_leap(int x)//判断x是否为闰年
{
if(x%100==0)
{
if(x%400==0) return 1;
else return 0;
}
else
{
if(x%4==0) return 1;
else return 0;
}
}
int day[10]={3,5,7,11,13,17,19,23,29,31};
//存储日为质数的数 可以提前预处理
int month[1000],cnt1;
//存储日+月为质数的数 估计数组大小(实际为38)
int year[100000],cnt2;
//存储日+月+年为质数的数 估计数组大小 (实际为55157)
void init()//预处理出所有满足条件的数 存储在year数组中
{
for(int i=1;i<=12;i++)
{
int t;
if(i==1||i==3||i==5||i==7||i==8||i==10||i==12) t=10;
else if(i==4||i==6||i==9||i==11) t=9;
else if(i==2) t=8;
//根据大小月来判断要枚举到day数组中的第几个
//这里没有考虑2月29日的情况 之后单独处理闰年
for(int j=0;j<t;j++)
{
int tmp=i*100+day[j];//计算出月+日之后的数
if(is_prime(tmp))//如果是质数 加入数组
month[cnt1++]=tmp;
}
}
for(int i=1;i<=9999;i++)
{
if(is_leap(i))//如果是闰年 要先单独处理0229
{
int tmp=i*10000+229;//xxxx0229
if(is_prime(tmp))//如果是质数 加入数组
year[cnt2++]=tmp;
}
//枚举月+日为质数的数 判断加上年之后还是不是质数
for(int j=0;j<cnt1;j++)
{
int tmp=i*10000+month[j];
if(is_prime(tmp))//如果是质数 加入数组
year[cnt2++]=tmp;
}
}
}
int main()
{
freopen("wonder.in","r",stdin);
freopen("wonder.out","w",stdout);
init();
int T;
cin>>T;
while(T--)
{
int ans=0;
string s;
cin>>s;
//枚举每个满足条件的数 看看是否能够由s构造出来
for(int i=0;i<cnt2;i++)
{
int now=year[i];//取出这个数
bool flag=1;//flag=1表示这个数满足条件 否则不满足
for(int j=7;j>=0;j--)
{
int x=now%10;//取出now的从左往右数第j位
now/=10;
//如果对应位置上数不相等且该位置不是'-'
if(x!=s[j]-'0'&&s[j]!='-')
{
flag=0;//这个数一定不满足条件
break;
}
}
if(flag) ans++;
}
cout<<ans<<endl;
}
return 0;
}
/*
思路:
预处理出所有的答案 然后对于每个输入的数验证在答案数组中有几个满足要求
预处理方法:
首先 找到为质数的可以当日的数:3 5 7 11 13 17 19 23 29 31
(2不可以 因为就算日为质数 月+日也一定不为质数)
然后 枚举1~12个月 找到为质数的月+日的数
然后 枚举1~9999年 找到为质数的年+月+日的数
以上为出题人思路 原题时间限制为4s 可以通过
*/