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

## 题意

$q$ 次询问，给定一个数 $r$。求从公元前 4713 年 1 月 1 日起 $r$ 天后的日期。

特别的：

- 公元 1582 年 10 月 15 日（含）以后：与现在相同。
- 公元 1582 年 10 月 5 日（含）至 10 月 14 日（含）：不存在，这些日期被删除。
- 公元 1582 年 10 月 4 日（含）以前：年份是 $4$ 的倍数就是闰年。
- 公元零年并不存在，因此公元前 1 年、前 5 年、前 9 年、前 13 年……以此类推的年份应视为闰年。

## 做法

从公元前 4713 年 1 月 1 日到公元 1582 年 10 月 4 日，总共的天数不超过 $3 \times 10^6$。因此我们可以预处理。注意处理公元零年和闰年。

从公元 1582 年 10 月 15 日以后，注意到每 400 年都是一个循环。因此再预处理从公元 1582 年 10 月 15 日以后 400 年的日期与公元 1582 年 10 月 15 日的**偏移量**。查询时求 $r \bmod (365 \times 400 + 97)$ 即可。

```cpp
// Problem: 
//     P7075 [CSP-S2020] 儒略日
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7075
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2299160, M = 365 * 400 + 97;

struct Day {
	int y, m, d;
	
	Day() {}
	Day(int a, int b, int c) {
		y = a;
		m = b;
		d = c;
	}
	
	bool operator ==(const Day &h) const {
		return y == h.y && m == h.m && d == h.d;
	}
	
	bool operator !=(const Day &h) const {
		return y != h.y || m != h.m || d != h.d;
	}
	
	bool operator <(const Day &h) const {
		return y < h.y || y == h.y && m < h.m || y == h.y && m == h.m && d < h.d;
	}
}res[N + 114514], delta[M + 114514];

bool leap(int x) {
	if (x > 1582) return x % 4 == 0 && x % 100 || x % 400 == 0;
	return (x + (x < 0)) % 4 == 0;
}

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

Day add(Day t) {
	if (t == Day(-1, 12, 31)) return Day(1, 1, 1);
	if (t == Day(1582, 10, 4)) return Day(1582, 10, 15);
	
	int y = t.y, m = t.m, d = t.d;
	if (m == 12 && d == 31) return Day(y + 1, 1, 1);
	
	d ++ ;
	if (d > days[m] + (m == 2 && leap(y))) {
		d = 1, m ++ ;
	}
	if (m > 12) {
		m = 1, y ++ ;
	}
	
	return Day(y, m, d);
}

void initN() {
	Day d = {-4713, 1, 1};
	int cnt = 0;
	while (d != Day(1582, 10, 15)) {
		res[cnt ++ ] = d;
		d = add(d);
	}
}

void initM() {
	Day d = {1582, 10, 15};
	int cnt = 0;
	while (cnt < M) {
		delta[cnt ++ ] = Day(d.y - 1582, d.m, d.d);
		d = add(d);
	}
}

void print(Day t) {
	cout << t.d << ' ' << t.m << ' ' << abs(t.y);
	if (t.y < 0) cout << " BC";
	cout << '\n';
}

signed main() {
	initN();
	initM();
	
	int q;
	cin >> q;
	while (q -- ) {
		int r;
		cin >> r;
		if (r <= N) print(res[r]);
		else {
			r -= N;
			-- r;
			// 1582.10.15 后的第 r 天（10.15 是第 0 天）
			Day t = delta[r % M];
			t.y += r / M * 400;
			t.y += 1582;
			print(t);
		}
	}
	return 0;
}
```

正在渲染内容...