这篇文章主要收录一些不算奇淫技巧的小tips,这种比较散乱的小知识点记起来还是需要系统化

蔡勒公式（时间转换到星期几）

学校oj有很多时间转换的题目但是这个可以说知道公式就秒了，如果自己思考实现还是要费一点时间。更巧的是算法期中考完试在楼道还捡到了一张小纸条，就赫然写着这个公式。有种低山臭水遇知音感英雄所见略同感。
蔡勒（Zeller）公式是一个非常有名的数学公式，可以直接根据日期（年、月、日）算出那天是星期几。

公式

$$W = (d + 2m + 3(m+1)/5 + y + y/4 - y/100 + y/400 + 1) \bmod 7$$

  • $y$：年份
  • $m$：月份
  • $d$：日期
  • $W$：结果。0代表周日，1代表周一，2代表周二…以此类推，6代表周六。

潜规则

蔡勒公式有一个非常特殊的规定，如果你忘了这一步，算出来全是错的：

如果月份是 1月 或 2月，必须把它们看作是前一年的 13月 和 14月。

  • 比如：2024年 1月 20日 $\rightarrow$ 看作 2023年 13月 20日。
  • 比如：2024年 2月 10日 $\rightarrow$ 看作 2023年 14月 10日。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
int getWeekday(int y, int m, int d) {
    // 潜规则：1, 2月要当成上一年的13, 14月
    if (m == 1 || m == 2) {
        m += 12;
        y--;
    }
    
    // 蔡勒公式核心逻辑
    int w = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400 + 1) % 7;
    
    return w; // 0=日, 1=一, 2=二, 3=三, 4=四, 5=五, 6=六
}

为什么这么写（公式解释）

乍一看可能有点不知所云，变量还不少，you’re not alone。上面这个公式已经可以直接用了，但想弄明白它为什么对，得看更严谨的标准形式：

标准形式（公历）

$$W = \left( y + \lfloor \frac{y}{4} \rfloor + \lfloor \frac{c}{4} \rfloor - 2c + \lfloor \frac{26(m+1)}{10} \rfloor + d - 1 \right) \pmod 7$$

变量含义：

  • $W$：星期几。计算结果：0-周日，1-周一，2-周二，3-周三，4-周四，5-周五，6-周六。
    • 注意：有的版本计算结果 0 是周六，这取决于公式末尾是 -1 还是其他的修正值。
  • $c$：世纪数减 1（即年份的前两位）。例如 2024 年，$c=20$。
  • $y$：年份的后两位。例如 2024 年，$y=24$。
  • $m$：月份。重要： 1月和2月要看作上一年的13月和14月（此时年份 $y$ 和世纪 $c$ 也要相应按上一年计算）。
  • $d$：日。
  • $\lfloor \rfloor$：表示向下取整（在 C++ 中整数除法自动实现这一点）。

各项的物理意义（为什么这么写？）

蔡勒公式本质上是在算**“总偏移天数”**：

  1. $d$：每过一天，星期往后移一天。
  2. $y + \lfloor \frac{y}{4} \rfloor$：
    • 每过一个平年，星期移 1 天（$365 \pmod 7 = 1$）。
    • 每 4 年多出的闰日。
  3. $\lfloor \frac{26(m+1)}{10} \rfloor$：
    • 核心黑科技。用来处理每个月天数不规则（30或31）产生的偏移。
    • 它利用 1、2 月挪到岁末的技巧，使得 3-14 月的长度呈现出极其稳定的数学规律。
  4. $\lfloor \frac{c}{4} \rfloor - 2c$：
    • 处理世纪闰年的规则：每 100 年不闰，每 400 年再闰。
    • 这一项专门校准长达百年的时间误差。

龟速乘 / 快速乘

快速幂是「倍增地乘」，而龟速乘是用加法代替乘法，防止 a * b 在取模前溢出 long long（常见于 a * b % mod 且 mod 很大的时候）。

1
2
3
4
5
6
7
8
9
long long mul(long long a, long long b, long long p) {
    long long ans = 0;
    while (b) {
        if (b & 1) ans = (ans + a) % p;   // 当前位是 1，累加
        a = (a + a) % p;                  // a 变成 a×2，对应下一位的权重
        b >>= 1;                          // 处理下一位
    }
    return ans;
}

二进制最高位 1 的位置

用 __builtin_clz（count leading zeros）可以 O(1) 求出 n 的二进制最高位是第几位：

1
int wei = 31 - __builtin_clz(n);   // int 是 32 位，减去前导 0 的个数

埃氏筛预处理质数

打表时最常用的筛法，$O(n \log \log n)$。注意外层循环到 i * i < N 就够了，从 i * i 开始筛：

1
2
3
4
5
6
7
8
9
10
11
bool prime[N];
fill(prime, prime + N, true);
prime[0] = prime[1] = false;

for (int i = 2; i * i < N; i++) {
    if (prime[i]) {
        for (int j = i * i; j < N; j += i) {
            prime[j] = false;
        }
    }
}

这三条都属于「知道就秒、不知道就卡」的小碎片，先归进这篇随记，之后多了再拆。