牛客练习赛37

发表于 更新于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

A.筱玛的快乐

题目描述：

筱玛是个快乐的男孩子。寒假终于到了，筱玛决定请他的朋友们一起来快乐。对于筱玛来说，最快乐的事情莫过于翻看万年历上的日期了。一个日期是“快乐”的，当且仅当这一年的年份是一个质数，且将月份、日期写成”MM-DD”的形式后是对称的。如：”2003-01-10”是“快乐”的。筱玛有n个小伙伴，每个小伙伴都会提出一个问题，即：从”2000-01-01”这一天开始，第k个“快乐”的日期是什么。

输入描述:

第一行一个整数n。接下来n行，每行一个数字k，表示一次询问。

输出描述:

输出共n行，每行一个形如”YYYY-MM-DD”的日期表示答案。

输入：

1
2
3
4
3
1
23
48

输出：

1
2
3
2003-01-10
2027-11-11
2063-12-21

备注:

1≤n≤$10^6$，保证答案存在且答案年份为4位数。

思路：

线性筛$O(1)$打表，坑：卡C++的输入输出，要用C语言的输入输出==

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn=3e6+5;
const LL maxm=166670;
int T,n;vector<LL> ans;bool isp[maxn];LL cnt=0,prime[maxn];
char str[6][8]={"-12-21","-01-10","-02-20","-03-30","-10-01","-11-11"};
void euler_sieve(){
    memset(isp,true,sizeof(isp));
    memset(prime,0,sizeof(prime));
    isp[0]=isp[1]=false;
    for(LL i=2;i<maxn;++i){
        if(isp[i])prime[cnt++]=i;
        for(LL j=0;j<cnt&&i*prime[j]<maxn;++j){
            isp[i*prime[j]]=false;
            if(i%prime[j]==0)break;
        }
    }
}
int main(){
    euler_sieve();ans.clear();
    for(LL i=0,num=0;num<maxm&&i<cnt;++i)
        if(prime[i]>2000LL)ans.push_back(prime[i]),num++;
    while(~scanf("%d",&T)){
        while(T--){
            scanf("%d",&n);
            printf("%lld%s\n",ans[n/6+(n%6>0)-1],str[n%6]);
        }
    }
    return 0;
}
0%