题目理解

问题描述

给定一个儒略日数值 $r$（从公元前4713年1月1日正午12点开始计算的天数），要求计算出对应的公历日期。

历法规则

1. 公元前4713年1月1日 ~ 公元1582年10月4日：使用儒略历

   • 每月天数与现行公历相同
   • 年份是4的倍数即为闰年
   • 没有公元0年（公元前1年之后是公元1年）

2. 公元1582年10月5日 ~ 10月14日：不存在（被删除的10天）

3. 公元1582年10月15日以后：使用格里高利历

   • 闰年规则：能被400整除，或能被4整除但不能被100整除

解题思路

方法一：二分查找 + 模拟（推荐）

这是最直观的解法，分为三个历史时期处理：

1. 儒略历时期（r < 2299160）

从公元前4713年1月1日开始，逐年计算：

// 伪代码
year = -4712;  // 公元前4713年
days_remaining = r;

while (days_remaining >= 365) {
    leap = isJulianLeap(year) ? 1 : 0;
    if (days_remaining >= 365 + leap) {
        days_remaining -= 365 + leap;
        year++;
    } else {
        break;
    }
}

// 然后在year年中逐月计算

2. 缺失的10天

儒略日2299160对应1582年10月4日，下一个就是2299161对应1582年10月15日。

3. 格里高利历时期（r >= 2299161）

从1582年10月15日开始计算，需要跳过缺失的10天：

if (r >= 2299160) {
    r += 10;  // 跳过缺失的10天
}

方法二：数学公式法（高效）

利用周期性质进行快速计算：

儒略历周期

• 4年一个周期：1461天（365×3 + 366）
• 可以先计算经过了多少个4年周期

格里高利历周期

• 400年一个周期：146097天
• 可以利用这个周期快速计算年份

关键实现细节

1. 闰年判断

// 儒略历闰年
bool isJulianLeap(int y) {
    if (y < 1) y = 1 - y;  // 处理公元前年份
    return y % 4 == 0;
}

// 格里高利历闰年
bool isGregorianLeap(int y) {
    return (y % 400 == 0) || (y % 4 == 0 && y % 100 != 0);
}

2. 月份天数计算

int getDays(int y, int m, bool isGregorian) {
    if (m == 2) {
        if (isGregorian) return isGregorianLeap(y) ? 29 : 28;
        else return isJulianLeap(y) ? 29 : 28;
    }
    return mon[m];  // mon数组存储各月天数
}

3. 输出格式

• 公元后：Day Month Year
• 公元前：Day Month Year BC

完整算法步骤

1. 读入儒略日 r
2. 判断历法时期
   • 如果 r < 2299160：使用儒略历，从公元前4713年开始
   • 否则：使用格里高利历，跳过1582年缺失的10天，从1582年10月15日开始
3. 计算年份
   • 先计算整年数（利用周期性质加速）
   • 再处理剩余天数
4. 计算月份和日期
   • 在当前年份中逐月减去天数
5. 格式化输出
   • 注意公元前年份要加"BC"

复杂度分析

• 时间复杂度：$O(Q \cdot \log(\text{最大年份}))$ 或 $O(Q)$（取决于实现方法）
• 空间复杂度：$O(1)$

示例解析

样例1

输入：10
计算：从公元前4713年1月1日过10天
输出：11 1 4713 BC

边界情况

• r = 0：公元前4713年1月1日
• r = 2299159：1582年10月4日（儒略历最后一天）
• r = 2299160：1582年10月15日（格里高利历第一天）

实现技巧

1. 统一处理公元前年份：可以用负数表示公元前年份，输出时再转换
2. 利用周期加速：对于大数据，使用400年周期或4年周期快速计算
3. 预处理月份前缀和：可以预处理每月天数的前缀和，加速日期计算
4. 注意整数溢出：儒略日可能很大，使用64位整数