同余最短路-入门两题

P3403跳楼机

传送门：https://www.luogu.com.cn/problem/P3403

题目大意：一个线段为[0,h - 1].你从0开始，每次可以朝任意方向走 x , y , z步。(前提是在线段内)。 问你有多少个整数点是可以到达的。(x , y , z <= 1e5 , h <= 1e15).

题目思路:

首先，由于h过大，不能直接dp递推。所以自然考虑 在 mod x 剩余系下 求解问题。 那么不管 y , z 走多少次。最终都会落在 mod x 的剩余系中。那问题规模就变小了。 

显然，可能 mod x 的剩余系中 有些值永远取不到。但值一旦第一次被取到，那么所有在本剩余系中的所有值都能被取到(通过 + x 转移)。

那么问题转化为： 

有了本转移方程，我们可以直接在剩余系中跑最短路。 然后推推公式计算即可。

拓展:P2662 牛场围栏

传送门：https://www.luogu.com.cn/problem/P2662

题目大意：给你若干个数。问你这些数中最大的不能被凑出来的数.

题目思路：

当 时，有无限个数组合不出来.

还是一样的状态,找最小值M作为剩余系：

考虑最后如何求答案?

假设答案存在于剩余系i中。 由于已知  .

所以最大的不能被凑出来的数为: f(i) - M.

最终答案为：