同余最短路学习笔记

感觉这个东西的构造好巧妙啊qwq
那就写篇博客记一下吧qwq

P3403 跳楼机

设 \(d_i\) 表示模 \(x\) 为 \(i\) 的能到达的最小楼层。
那么

• \(i\xrightarrow{y} (i+y)\mod x\)
• \(i\xrightarrow{z} (i+z)\mod x\)

起点为 \(d_1=1\)，跑最短路。

[ABC077D] Small Multiple

任何一个整数都可以由 \(1\) 通过 \(\times 10\)，\(+1\) 交替操作若干次得到。
观察到，第一种操作不改变数位和，第二种操作使数位和加 \(1\)。
那么可以连边：

• \(i\xrightarrow{0} (i\times 10) \mod k\)
• \(i\xrightarrow{1} (i+1)\mod k\)

初始条件为 \(dis_1=1\)，答案为 \(dis_0\)。