题目描述

为了简便计算，天文学家们使用儒略日（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