败犬日报 2026-02-26

1. std::gcd 的欧几里得算法和 stein 算法

欧几里得算法大家应该比较熟，是不断取模；新版 GCC 且标准 C++20 之后用了 stein 算法，不断去除公共 2 因子并相减。

stein 算法平均意义上更快，取模的开销太大了。但是特定输入比如 gcd(1, 0x7fffffff)，stein 要循环个 31 次，欧几里得 1-2 次就做完了。

上面文章作者大概就是被这种输入 hack 了。