洛谷5440 [XR-2]奇迹

题意

给出一个残缺的日期，求使得日、月+日、年+月+日都为质数的填充方案数。

多组数据，$T\le 10$ 。

题解

先预处理出所有合法的日期，然后对于输入直接枚举即可。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int t,cnt,zs[100005],pre_mxday[13];
char s[10];
bool ss[100005],ok[10000][13][32];

inline void get_prime()
{
    memset(ss,1,sizeof(ss));
    ss[0]=ss[1]=0;
    for (int i=2;i<=100000;i++)
    {
        if (ss[i]) zs[++cnt]=i;
        for (int j=1;j<=cnt && zs[j]*i<=100000;j++)
        {
            ss[zs[j]*i]=0;
            if (i%zs[j]==0) break;
        }
    }
}

inline bool check(int x)
{
    if (x<=100000) return ss[x];
    for (int i=1;zs[i]*zs[i]<=x;i++) if (x%zs[i]==0) return 0;
    return 1;
}

inline void pre()
{
    for (int i=1;i<=12;i++) pre_mxday[i]=30;
    pre_mxday[2]=28;
    pre_mxday[1]=pre_mxday[3]=pre_mxday[5]=pre_mxday[7]=pre_mxday[8]=pre_mxday[10]=pre_mxday[12]=31;
    for (int year=1;year<=9999;year++)
    {
        bool is_r=0;
        if ((year%4==0 && year%100) || year%400==0) is_r=1;
        for (int mon=1;mon<=12;mon++)
        {
            int mxday;
            if (is_r && mon==2) mxday=29;
            else mxday=pre_mxday[mon];
            for (int day=1;day<=mxday;day++)
            {
                if (!check(day)) continue;
                int now=mon*100+day;
                if (!check(now)) continue;
                now=year*10000+now;
                if (!check(now)) continue;
                ok[year][mon][day]=1;
            }
        }
    }
}

signed main()
{
    t=read();
    get_prime();
    pre();
    while (t--)
    {
        scanf("%s",s+1);
        int ans=0;
        for (int year=1;year<=9999;year++)
        {
            int y=year; bool flag=0;
            for (int i=4;i;i--)
            {
                if (s[i]=='-' || s[i]-'0'==y%10) y/=10;
                else
                {
                    flag=1;
                    break;
                }
            }
            if (flag) continue;
            for (int mon=1;mon<=12;mon++)
            {
                if (s[5]!='-' && s[5]-'0'!=mon/10) continue;
                if (s[6]!='-' && s[6]-'0'!=mon%10) continue;
                for (int day=1;day<=31;day++)
                {
                    if (s[7]!='-' && s[7]-'0'!=day/10) continue;
                    if (s[8]!='-' && s[8]-'0'!=day%10) continue;
                    if (ok[year][mon][day]) ans++;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}