自动搬运

查看原文

来自洛谷，原作者为

	xht 好想爱这个世界啊

搬运于2025-08-24 22:10:46，当前版本为作者最后更新于2019-06-29 20:56:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

求满足“日”组成的两位数，“月+日”组成的四位数，“年+月+日”组成的八位数均为质数的日期的个数。

前置知识

• 乱搞搜索
• 质数

题解

略...

只要保证正确性且不会超时得太过分都能 AC

别问我部分分有啥用，我也不知道

两个易错点：

1. $29$ 为质数，$229$ 也为质数，因此要正确判断闰年。值得一提的是，$3200,6400,9600$ 年是否为闰年存在争议，但并不影响本题，因为 $32000229,64000229,96000229$ 均不是质数。
2. $1$ 不是质数，因此“日”不能为 $1$。

代码

#include <bits/stdc++.h>
using namespace std;
const int p[] = {0,3,5,7,11,13,17,19,23,29,31,37};
const int d[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int T, a[66], t, ans[66666], tot;
char s[10];

inline bool is_prime(int x) {
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return 0;
    return 1;
}

int main() {
    ios::sync_with_stdio(0);
    for (int i = 1; i <= 12; i++)
        for (int j = 1; p[j] <= d[i]; j++)
            if (is_prime(i * 100 + p[j]))
                a[++t] = i * 100 + p[j];
    for (int i = 4; i <= 9999; i += 4)
    	if ((i % 100 || !(i % 400)) && is_prime(i * 10000 + 229))
    		ans[++tot] = i * 10000 + 229;
    for (int i = 1; i <= 9999; i++)
        for (int j = 1; j <= t; j++)
            if (is_prime(i * 10000 + a[j]))
                ans[++tot] = i * 10000 + a[j];
    cin >> T;
    while (T--) {
        cin >> (s + 1);
        int cnt = 0;
        for (int i = 1; i <= tot; i++) {
            int now = ans[i], flag = 1;
            for (int j = 8; flag && j; j--, now /= 10)
                if (s[j] != '-' && s[j] - '0' != now % 10)
                    flag = 0;
            cnt += flag;
        }
        cout << cnt << endl;
    } 
    return 0;
}