2025.08.27打卡Day286

健康

• 11 点睡，8 点半起床。
• 午睡 1 小时。
• 俯卧撑 100 + 仰卧起坐 100。

娱乐

• xin 计划。

算法

Codeforces：

• https://codeforces.com/problemset/problem/251/C ，2000 分，注意到选择模数 mod 进行操作 2 之后，a 会变成 mod 的倍数，且是小于 a 的最大的 mod 的倍数。因此，通过不断进行操作 2，到达不超过 a 的 1...k 的公倍数之后，就必须得用操作 1 才能继续减小了。因此，问题变成了从 a 先变到一个不超过自己的最大的模数的公倍数，然后一直经历公倍数，最后变成 b 的最小操作次数。注意到最小公倍数不超过 4e5，所以这三段都可以预处理，使用 DP 即可。

其他：

• 复习了扩展欧几里得以及扩展中国剩余定理等算法的原理，进行了完全的重新推导，形成了博客笔记。