蔡勒公式

· · 算法·理论

先叠个甲，本文非转载，但是参考了这篇文章。这篇文章讲的很好，建议大家去学习支持一下作者。（我就是从里面学的）

前铺知识

正片开始

A：他今年什么时候过生日啊？ B：今年 6 月 14 号 A：那一天上学吗？ B：我哪知道？我看看……（开始翻日历） C：嗯……星期六，不上学。 B：你是怎么知道的？！ C：算出来的啊……

简介

蔡勒公式，是一种可以快速计算某一天是星期几的公式。其形式如下：（如果不想看证明可以直接拿来用）

\begin{aligned} D &= \Big[\frac{c}{4}\Big] - 2c + y + \Big[\frac{y}{4}\Big] + \Big[\frac{13(m + 1)}{5}\Big] + d - 1 \\ W &= D \bmod 7 \end{aligned}

其中：

\begin{aligned} D &= \Big[\frac{20}{4}\Big] - 2 \times 20 + 25 + \Big[\frac{25}{4}\Big] + \Big[\frac{13 \times (6 + 1)}{5}\Big] + 14 - 1 \\ &= 5 - 40 + 25 + 6 + 18 + 14 - 1 \\ &= 27 \\ 27 &\bmod 7 = 6 \end{aligned}

所以是星期六。 翻翻日历，你会惊奇发现，真的是星期六。 你也可以再随便带入几个日期自己算一算。 这个公式适用于任何年份，任何日期。计算简单，口算就可以（最难算的应该就是 [\frac{13(m + 1)}{5}] 了……）。这个公式请牢记于心，说不定哪一天真的能够派上用场。

如果你到此已经满足了，那么你可以关掉这个文章并继续干其他的事情。 当然，大部分情况下，你会满脸问号，盯着上面那个神奇的公式发愣。然后渐渐说出三个字：为什么？ 然后剧烈的求知欲就会驱使你继续往下读。 那么，准备好了吗？

证明

如果不知道蔡勒公式，也不能使用日历，能不能求出某一天是星期几呢？ 比方说 6 月 14 日。你知道 5 月 30 号是端午节的前一天，并且是周五。算一算，5 月 30 日到 6 月 1 日过了 2 天（5 月是大月），而 6 月 1 日到 6 月 14 日过了 13 天。掐指一算，一共过了 15 天。15 \bmod 7 = 1，而 5 + 1 = 6，所以 6 月 14 日是周六。 仔细回顾我们计算的过程，我们先取了一个原点（5 月 30 日），然后计算了到六月的距离，然后计算 6 月 1 日到 14 日的距离，我们将总偏移量记为 D_3。如果说我们取的原点和当前日期不在同一年（比方说 2023 年），那么还得计算出原点到原点年份的下一年 1 月 1 日（D_1），再从下一年 1 月 1 日于当前日期所在年份 1 月 1 日的偏移量（记为 D_2）。总偏移量 \textbf D 就是 \textbf D_1 + \textbf D_2 + \textbf D_3。 可以看下面草图方便理解：

如果我们把原点选在某一年的 12 月 31 日，就可以省去 D_1 的计算了。并且，由于我们再计算最后日期的时候，需要拿 D \bmod 7 去加上原点的星期数才能得到目标日期。如果说是星期日，我们就可以省去计算了。 所以我们需要找一个原点符合以下两个条件：

由于我们取的原点**后一年是 01 年 1 月 1 日**，所以 $D_2$ 是 $y - 1$ 年，一年 $365$ 天，所以 $D_2 = 365 \times (y - 1)$，再考虑闰年的影响，即可得到： $$ D_2 = (y - 1) \times 365 + \Big[\frac{y - 1}{4}\Big] - \Big[\frac{y - 1}{100}\Big] + \Big[\frac{y - 1}{400}\Big] $$ $365$ 后面的计算是因为**四年一闰，百年不闰，四百年又闰**。所以通过一个加减法算式来得到最终结果。 $D_2$ 计算到此结束。 ## 计算 $D_3 为了计算出 $D_3$，我们先得分析一下月份的规律。$D_3$ 主要考察的是从**一年的开始到某月之前的总时间**，类似算法中的前缀和，我们将这个前缀和数组记为 $S$，而为了方便计算，我们还得先计算每个月的天数，记为 $A$。由于不考虑闰年的话，天数最少的是 2 月，只有 28 天，因此不妨**以 28 为起点来计算**（比方说 1 月有 31 天，我们就将天数当作是是 3，因为 $31 - 28 = 3$，计算更方便）。 如果说你用大脑或程序算了亿下的话，你将会收获一个表格： | 月份 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | | :----: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | | **天数** | 31 | 28 | 31 | 30 | 31 | 30 | 31 | 31 | 30 | 31 | 30 | 31 | | $A$ | 3 | 0 | 3 | 2 | 3 | 2 | 3 | 3 | 2 | 3 | 2 | 3 | | $S$ | 0 | 3 | 3 | 6 | 8 | 11 | 13 | 16 | 19 | 21 | 24 | 26 | 仔细观察，可以发现 $A$ 从 3 月开始就是 3 2 3 2 3 的循环，$S$ 的增幅也从 3 月开始呈现 3 2 3 2 3 的循环。$3 + 2 + 3 + 2 + 3 = 13$，而这过去了 5 个月，于是数学家非常大胆的写了一个函数： $$ f(x)=\Big[\frac{13}{5}x\Big] $$ 然后让 $x$ 从 4 开始，列出 $f(x)$ 的值： | x | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | | :------: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | | **f(x)** | 10 | 13 | 15 | 18 | 20 | 23 | 26 | 28 | 31 | 发现了什么？ $f(x) = S_{x - 1} + 7$！ 这意味着，$f(x)$ 不仅于 $S$ 数组有着相同的增幅，甚至数字每次都刚好差 7，那这，无疑对我们的计算有着巨大的帮助。 > 事实上，这只是众多构造方法中的一种，读者也可以自己研究其他构造方法。 至此，我们收获了： $$ D_3 = \begin{cases} d & m = 1 \\ 31 + d & m = 2 \\ (m - 1) \times 28 + \Big[\frac{13(m + 1)}{5}\Big] - 7 + d + i & m \ge 3 \end{cases} $$ 注：$i = 1$ 时为闰年，$i = 0$ 时为平年。主要在于一个调整的作用。 我们也可以调整一下，将 $1,2$ 月作为前一年的 $13,14$ 月，这样能够继续满足 3 2 3 2 3 的规律。 这样不仅仍然符合公式，而且 2 月变成了上一年的最后一个月，也就是公式中 $d$ 的部分，于是**平闰年的影响也去掉了**，公式简化成了： $$ D_3 = (m - 1) \times 28 + \Big[\frac{13(m + 1)}{5}\Big] - 7 + d $$ 其中 $3 \le m \le 14$。 ## 整合与化简 至此，你已历经 $n$ 大难关，马上就能收获神奇的蔡勒公式了！ 由于 $D = D_2 + D_3$，所以 $$ D = (y - 1) \times 365 + \Big[\frac{y - 1}{4}\Big] - \Big[\frac{y - 1}{100}\Big] + \Big[\frac{y - 1}{400}\Big] + (m - 1) \times 28 + \Big[\frac{13(m + 1)}{5}\Big] - 7 + d $$ 先别高兴太早，这个公式还有一个小问题：由于 1，2 月被当作去年 13，14 月算，所以**闰年的地方需要改进**。比方说 2024 年本来是闰年，如果计算 3 月 1 日的星期数，那么由于 2 月到了 23 年的 14 月，为了日期准确，应该让 23 年变成闰年，但是事实是 24 年依然是闰年。于是，V2 版横空出世： $$ D = (y - 1) \times 365 + \Big[\frac{y}{4}\Big] - \Big[\frac{y}{100}\Big] + \Big[\frac{y}{400}\Big] + (m - 1) \times 28 + \Big[\frac{13(m + 1)}{5}\Big] - 7 + d $$ 利用这个公式，我们就能**正确的求出星期数了**！ *** 但是你确定用这个公式计算会比翻日历快？简直太复杂了！ 由于最后的结果还得对 7 取模，根据同余定理，我们可以先给 $D$ 的各部分都对 7 取模！ $$ \begin{aligned} D &= (y - 1) \times 365 + \Big[\frac{y}{4}\Big] - \Big[\frac{y}{100}\Big] + \Big[\frac{y}{400}\Big] + (m - 1) \times 28 + \Big[\frac{13(m + 1)}{5}\Big] - 7 + d \\ &= (y - 1) \times (364 + 1) + \Big[\frac{y}{4}\Big] - \Big[\frac{y}{100}\Big] + \Big[\frac{y}{400}\Big] + \Big[\frac{13(m + 1)}{5}\Big] + d \\ &= (y - 1) + \Big[\frac{y}{4}\Big] - \Big[\frac{y}{100}\Big] + \Big[\frac{y}{400}\Big] + \Big[\frac{13(m + 1)}{5}\Big] + d \\ \end{aligned} $$ $(m - 1) \times 28$ 是 7 的倍数，可以直接不要，364 也是 7 的倍数，只保留一个 $y - 1$（也就是除了 364 剩下的那一个）即可。 至此，公式短小了很多。 这还不是最简练的形式，我们发现，每个世纪第一年 3 月 1 日的星期数就会重复一次，例如：公元 1 年、401 年、801 年，直到 2001 年，这些年 3 月 1 日都是星期四，而 101、501、901、到将来的 2101，都是星期二。从 201 开始，每个 4 个世纪就都会是星期天，而 301 开始则都是星期五。 换而言之，星期数总以 $4,2,0,5$ 的顺序循环。由于 $5 \equiv -2 \pmod 7$，所以可以理解为数列是 $4,2,0,-2$，正好是个等差数列。于是我们就可以得到每个世纪初 3 月 1 日的公式： $$ W = 4 - 2 \times (c \bmod 4) $$ $c$ 就是世纪数 - 1，即年份前两位。 联立前面的公式，得到： $$ [(y - 1) + \Big[\frac{y}{4}\Big] - \Big[\frac{y}{100}\Big] + \Big[\frac{y}{400}\Big] + 11] \bmod 7 = 4 - 2 \times (c \bmod 4) $$ 同余变换得到： $$ (y - 1) + \Big[\frac{y}{4}\Big] - \Big[\frac{y}{100}\Big] + \Big[\frac{y}{400}\Big] \equiv -2 \times (c \bmod 4) \pmod 7 $$ 这是因为左边的 11 与右边的 4 模 7 同余（都是 4），所以一并处理掉了。 那么我们是不是可以用短小精悍的 $-2 \times (c \bmod 4)$ 来替换前面计算年份的一大堆？ 所以，我们计算年份的公式 $D$ 就变成了：（令 $y$ 为年份后两位） $$ D = -2 \times (c \bmod 4) + (y - 1) + \Big[\frac{13(m + 1)}{5}\Big] + d $$ 这是因为我们最开始的公式只适用于每个世纪的第一年，所以需要加上 $(y - 1)$ 来调整。 我们再慢慢加上闰年的情况。由于 1 个世纪 100 年，所以不需要考虑四百年一闰（因为这已经融入进等差数列里了），所以只需要考虑四年一闰和百年不闰。我们尝试用 $\big[\frac{y}{4}\big]$ 来表示当前世纪闰年的年数，由于百年的末尾 $y = 00$，而 $0 \div 4 = 0$，所以这可以天然地满足百年不闰，并且其余时候都能够满足四年一闰这个要求。 所以，经过不停地化简过后的**完美公式**，横空出世！ $$ D = -2 \times (c \bmod 4) + (y - 1) + \Big[\frac{y}{4}\Big] + \Big[\frac{13(m + 1)}{5}\Big] + d $$ 当然，由于部分同学不会作取模运算，我们还得把取模转化成四则运算： $$ a \bmod b = a - \Big[a \div b\Big] \times b $$ 这个只要上过小学推清楚就不难，大家如果有不明白的可以自己推一推，当作今天的小作业吧。至此，整个公式变成： $$ \begin{aligned} D &= -2 \times (c - 4 \times\Big[\frac{c}{4}\Big]) + (y - 1) + \Big[\frac{13(m + 1)}{5}\Big] + d \\ &= 8 \times \Big[\frac{c}{4}\Big] - 2c + y - 1 + \Big[\frac{13(m + 1)}{5}\Big] + d \\ \end{aligned} $$ 同余处理掉 8： $$ D = \Big[\frac{c}{4}\Big] - 2c + y + \Big[\frac{13(m + 1)}{5}\Big] + d - 1 $$ 至此，我们得到了蔡勒公式的最终形式，与开头的标准公式一模一样！ 在推导的过程中，我们经过种种机遇巧合：365 - 1 竟然能被 7 整除！看似毫无规律的月份天数竟然也有周期！$\frac{13}{5}x$ 向下取整居然能够呈现出 3 2 3 2 3 的周期，并且恰好是月份天数 - 7！这些巧合，仿佛让蔡勒公式的诞生添上了玄学的一笔，仿佛这个公式的诞生就是世界的必然。我们经历了许多，也收获了许多。现在，记住这个公式，在朋友说出日期的一刹那，你要反应过来，是时候用巧合与理性搭建出一条由 What date 到 What day 的桥梁了！ # End $$ \begin{aligned} D &= \Big[\frac{c}{4}\Big] - 2c + y + \Big[\frac{13(m + 1)}{5}\Big] + d - 1 \\ W &= D \bmod 7 \end{aligned} $$