题解：P7075 [CSP-S2020] 儒略日

· · 题解

题意简述

给定若干个儒略日，记录它们的年月日表示。

分析

大致分为以下几个需要处理的时间段。

公元前

此时 x < 1721424。

通过与公元元年 1 月 1 日的距离反推。

首先可以计算得，1/1/1（年/月/日）的儒略日为 1721424，这两天的距离则为 1721424 - x（含 x，不含 1/1）。此时 4 年为一个周期，一个周期共有 1461 天。先加上 4\lfloor \frac{1721424 - x}{1461} \rfloor 年跳到一个整周期（此时我们会位于某一年的 1 月 1 日，而它的前一年为闰年），然后逐年向下减，找到第一个不晚于它的年初。

接下来，对剩余的负数取相反数，表示从这个 1 月 1 日（不含）到目标日期（包含）的天数。

我们可以用一个函数来计算一年中的某天对应的月和日。可以先计算出每个月天数的前缀和，然后二分查找月份，计算日期即可。

代码如下：

const int AverageYearsMonth[] = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365};
const int LeapYearsMonth[] = {0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366};
// 计算年内的某个日期
// 传入：从某年的 1/1 到目标日期的天数，左闭右开。
// 返回：月，日（可直接输出）
std::pair<int, int> calculateDateInYear(ll days, bool leap = false) {
    const int *YearMonth = leap? LeapYearsMonth: AverageYearsMonth;
    // 一个月中包含的天数恰好大于 days
    auto monthPointer = std::upper_bound(YearMonth, YearMonth + 13, days);
    auto month = std::distance(YearMonth, monthPointer);
    auto currentDay = days - YearMonth[month - 1] + 1;
    return {month, currentDay};
}

公元 1582 年 10 月 4 日（含）以前

此时 1721424\le x < 2299161 。

同样地，我们可以用 x-1721424 计算从 1/1/1 到目标日期的天数（左闭右开），周期和公元前相同。

跳过若干个整周期之后，我们需要向后拨若干年，找到最晚的一年，使得剩余天数大于等于 0。

计算月和日即可。

公元 1582 年 10 月 5 日（含）至 10 月 14 日（含）

这段日期不存在。

公元 1582 年 10 月 15 日（含）以后

此时 x\le 2299161。 首先可以注意到，历法的更改实际上只会影响 1583/1/1 之后的日期。在此之前的日期减去被删除的 10 天，当做儒略历处理即可。

首先计算出，1583/1/1 的儒略日为 2299239。

不妨先凑一个整，暴力逐年推到 1601/1/1，然后考虑周期。每一次跳过若干个整周期，都跳到目标年份向下取整。

对于一个 400 年（146097 天）的周期，特判 400 的倍数。

对于一个 100 年（36524 天）的周期，特判 100 的倍数。

接下来跳过若干个 4 年（1461 天）的周期，再逐年逼近即可。

剩余的数即为当年的 1 月 1 日到目标日期的距离（左闭右开），计算日期并输出。

代码

/**
 * @link https://www.luogu.com.cn/problem/P7075
 */

#include <bits/stdc++.h>
using ll = long long;

namespace Solution {
    int Q;

    const int AverageYearsMonth[] = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365};
    const int LeapYearsMonth[] = {0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366};

    bool isLeap(int year, bool usingGregorian=true) {
        if (year<0)  year++;
        if (not usingGregorian)
            return (year%4 == 0);
        else
            return (year%400 == 0) or (year%100!=0 and year%4==0);
    }
    // 计算年内的某个日期
    // 传入：从某年的 1/1 到目标日期的天数，左闭右开。
    // 返回：月，日（可直接输出）
    std::pair<int, int> calculateDateInYear(ll days, bool leap=false) {
        const int *YearMonth = leap? LeapYearsMonth: AverageYearsMonth;
        // 一个月中包含的天数恰好大于 days
        auto monthPointer = std::upper_bound(YearMonth, YearMonth + 13, days);
        auto month = std::distance(YearMonth, monthPointer);
        auto currentDay = days - YearMonth[month - 1] + 1;
        return {month, currentDay};
    }
    void BC(ll julian) {
        auto daysNegativeCount = 1721424 - julian;  // 到 1/1/1 的天数
        auto termsCount = daysNegativeCount / 1461;  // 周期（4 年）数量
        auto yearAbs = termsCount * 4;  // 年份的绝对值
        daysNegativeCount %= 1461;  // 向前拨回若干周期后剩余的天数；到某年的 1 月 1 日，该年份绝对值是 4 的倍数
        auto newDays = daysNegativeCount;  // 再拨回一年，这一年一定是一个闰年
        while (newDays > 0) {
            newDays = newDays - 365 - isLeap(-yearAbs-1, false);
            yearAbs++;
        }

        int dayIndex = 0 - newDays;  // 目标日期到那年 1 月 1 日的天数，左闭右开

        auto [month, day] = calculateDateInYear(dayIndex, isLeap(-yearAbs, false));
        printf("%d %d %lld BC\n", day, month, yearAbs);
    }
    void DC_WithJulianCalender(ll julian) {
        auto daysCount = julian - 1721424;  // 到 1/1/1 的天数
        auto termsCount = daysCount / 1461;  // 四年周期
        auto years = termsCount * 4 + 1;  // 此时是这一年的 1/1
        daysCount %= 1461;
        auto newDays = daysCount;
        // 向后拨若干年，直到这个数大于等于 0 时的最小值
        while (newDays - 365 - isLeap(years, false) >= 0) {
            newDays = newDays - 365 - isLeap(years, false);
            years++;
        }
        auto [month, day] = calculateDateInYear(newDays, isLeap(years, false));
        printf("%d %d %lld\n", day, month, years);
    }
    void DC_WithGregorianCalender(ll julian) {
        const auto newYearJulianDay = 2299249-10;  // 1583/1/1 的儒略日
        if (julian < newYearJulianDay) {
            DC_WithJulianCalender(julian+10);
            return;
        }
        auto daysAfterNewYear = julian - newYearJulianDay;  // 从 1583/1/1 开始，左闭右开
        // 先暴力推 17 年
        auto year = 1583LL;  // 当前处于 year/1/1
        while (daysAfterNewYear - 365 - isLeap(year) >= 0) {
            daysAfterNewYear = daysAfterNewYear - 365 - isLeap(year);
            year++;
            if (year == 1601)  break;
        }
        if (year > 1600) {
            // 对于一个 400 年的大周期
            const auto bigTermLength = 146097;
            auto bigTermCount = daysAfterNewYear / bigTermLength;
            daysAfterNewYear %= bigTermLength;
            year += bigTermCount * 400; assert(year%400==1);

            // 直接特判 400 年的倍数
            if (daysAfterNewYear >= bigTermLength - 366) {
                year += 399;
                auto [month, day] = calculateDateInYear(daysAfterNewYear - bigTermLength + 366, 1);
                printf("%d %d %lld\n", day, month, year);
                return;
            }

            // 100 年的中等周期
            const auto midTermLength = 36524;
            auto midTermCount = daysAfterNewYear / midTermLength;
            daysAfterNewYear %= midTermLength;
            year += midTermCount * 100;

            // 特判 100 的倍数
            if (daysAfterNewYear >= midTermLength - 365) {
                year += 99;
                auto [month, day] = calculateDateInYear(daysAfterNewYear - midTermLength + 365, 0);
                printf("%d %d %lld\n", day, month, year);
                return;
            }

            // 4 年
            const auto littleTermLength = 1461;
            auto littleTermCount = daysAfterNewYear / littleTermLength;
            daysAfterNewYear %= littleTermLength;
            year += littleTermCount * 4;
            while (daysAfterNewYear - 365 - isLeap(year) >= 0) {
                daysAfterNewYear = daysAfterNewYear - 365 - isLeap(year);
                year++;
            }
            auto [month, day] = calculateDateInYear(daysAfterNewYear, isLeap(year));
            printf("%d %d %lld\n", day, month, year);
        } else {
            auto [month, day] = calculateDateInYear(daysAfterNewYear, isLeap(year));
            printf("%d %d %lld\n", day, month, year);
        }
    }

    void solve() {
        std::cin >> Q;
        ll x;

        for (auto i = 0; i < Q; i++) {
            std::cin >> x;
            if (x < 1721424) {
                BC(x);// 1/1/1 BC 及以前
            } else if (x <= 2299160) {
                DC_WithJulianCalender(x);  // 适用儒略历
            } else {
                DC_WithGregorianCalender(x);  // 适用格里高利历
            }
        }
    }
}

int main() {
    Solution::solve();
    return 0;
}