题目描述

为了简便计算,天文学家们使用儒略日(Julian day)来表达时间。

所谓儒略日,其定义为从公元前 4713 年 1 月 1 日正午 12 点到此后某一时刻间所经过的天数,不满一天者用小数表达。若利用这一天文学历法,则每一个时刻都将被均匀的映射到数轴上,从而得以很方便的计算它们的差值。

现在,给定一个不含小数部分的儒略日,请你帮忙计算出该儒略日(一定是某一天的中午 $12$ 点)所对应的公历日期。

我们现行的公历为格里高利历(Gregorian calendar),它是在公元 $1582$ 年由教皇格里高利十三世在原有的儒略历(Julian calendar)的基础上修改得到的(注:儒略历与儒略日并无直接关系)。具体而言,现行的公历日期按照以下规则计算:

  1. 公元 $1582$ 年 $10$ 月 $15$ 日(含)以后:适用格里高利历,每年一月 $31$ 天、 二月 $28$ 天或 $29$ 天、三月 $31$ 天、四月 $30$ 天、五月 $31$ 天、六月 $30$ 天、七月 $31$ 天、八月 $31$ 天、九月 $30$ 天、十月 $31$ 天、十一月 $30$ 天、十二月 $31$ 天。其中,闰年的二月为 $29$ 天,平年为 $28$ 天。当年份是 $400$ 的倍数,或日期年份是 $4$ 的倍数但不是 $100$ 的倍数时,该年为闰年。

  2. 公元 $1582$ 年 $10$ 月 $5$ 日(含)至 $10$ 月 $14$ 日(含):不存在,这些日期被删除,该年 $10$ 月 $4$ 日之后为 $10$ 月 $15$ 日。

  3. 公元 $1582$ 年 $10$ 月 $4$ 日(含)以前:适用儒略历,每月天数与格里高利历 相同,但只要年份是 $4$ 的倍数就是闰年。

  4. 尽管儒略历于公元前 $45$ 年才开始实行,且初期经过若干次调整,但今天人类习惯于按照儒略历最终的规则反推一切 $1582$ 年 $10$ 月 $4$ 日之前的时间。注意,公元零年并不存在,即公元前 $1$ 年的下一年是公元 $1$ 年。因此公元前 $1$ 年、前 $5$ 年、前 $9$ 年、前 $13$ 年……以此类推的年份应视为闰年。


输入格式

第一行一个整数 $Q$,表示询问的组数。

接下来 $Q$ 行,每行一个非负整数 $r_i$ ,表示一个儒略日。


输出格式

对于每一个儒略日 $r_i$ ,输出一行表示日期的字符串 $s_i$ 。共计 $Q$ 行。 $s_i$的格式如下:

若年份为公元后,输出格式为 Day Month Year。其中日(Day)、月(Month)、年(Year)均不含前导零,中间用一个空格隔开。

若年份为公元前,输出格式为 Day Month Year BC。其中年(Year)输出该年份的数值,其余与公元后相同。


Input & Output ‘s examples

Input ‘s eg 1

3
10
100
1000

Output ‘s eg 1

11 1 4713 BC
10 4 4713 BC
27 9 4711 BC

Input ‘s eg 2

3
2000000
3000000
4000000

Output ‘s eg 2

14 9 763
15 8 3501
12 7 6239

分析

把这题放 T1 的组题人就该拖出去捶一顿算完

大模拟,但单纯 Day By Day 的模拟得分很低。

看数据范围不难发现需要 $O(1)$ 或 $O(\log n)$ 的回答单次询问,但 $O(1)$ 做法代码难度较大,且不方便考场调试。故笔者提供一种较为好写的 $O(q \log n)$ 做法。

考虑二分年份。确定年份之后,剩下的日期最多也就 $365$ 天,暴力处理即可。

考虑如何判断当前年份与目标年份的相对大小。显然,我们只需要计算当前天数到二分年份的 $1$ 月 $1$ 日的天数即可。

但直接做的话在进入公元时会出问题,因为公元 $0$ 年并不存在。为了避免使用公元 $0$ 年,我们考虑将公元前的年份前移一年,最后算完之后若在公元前则减去一年即可。

那么就有

其中 $cnt$ 为闰年的数目。

考虑如何快速计算闰年的数目。首先先算出 $4$ 的倍数的年数,即 $\lceil \frac{x + 4712}{4} \rceil$

之后减去 $1583$ 年之后的整百年份,即 $\lceil \frac{x - 1600}{100} \rceil$

之后加上 $1583$ 年之后能被 $400$ 整除的年份,即 $\lceil \frac{x - 1600}{400} \rceil$

还有什么的话,就是 所有变量都需要 long long

题目细节较多,建议对照代码仔细理解。


Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
char c = getchar(), f = 0; x = 0;
while (!isdigit(c)) f = (c == '-'), c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 100000 + 5;
const int HA = 998244353;

ll ans = 0 , y = -4713 , m = 1 , d = 1;

const int days[] = {0 , 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31};

bool check_RUN(int x){ //判断闰年
if(x <= 0){
x *= -1;
return x % 4 == 1;
}
else {
if(x <= 1582) return x % 4 == 0;
else return (x % 400 == 0) || ((x % 4 == 0) && (x % 100 != 0));
}
}

ll check(int x){ //计算当前年份1月1日对应的天数
ll day = 0;
day += 1ll * (x + 4712) * 365;
if(x > 1582) day -= 10;
day += 1ll * (x + 4712 + 3) / 4;
if(x >= 1600){
x -= 1601;
day += x / 400;
day -= x / 100;
}
return day;
}

void get_day(){ //暴力模拟天数
d ++;
if(y == 1582 && m == 10 && d == 5) d += 10;
if(d > days[m] + (check_RUN(y) && m == 2)) m ++ , d = 1;
if(m > 12) y ++ , m = 1 , d = 1;
}

void solve() {
int n; read(n);
m = 1 , d = 1;
ll l = -4712 , r = 1e9 + 10;
while(l <= r){
ll mid = (l + r) >> 1;
if(check(mid) > n){
r = mid - 1;
}
else l = mid + 1 , y = mid;
}
n -= check(y);
if(y <= 0) y -= 1;
rep(i , 1 , n) {
get_day();
}
if(y <= 0) printf("%lld %lld %lld BC\n" , d , m , -y);
else printf("%lld %lld %lld \n" , d , m , y);
}

int main() {
#ifdef LOCAL
freopen("try.in" , "r" , stdin);
freopen("try1.out" , "w" , stdout);
#endif
int t; read(t);
while(t --) solve();

return 0;
}

THE END