被[国家集训队]墨墨的等式吊打力~

---

例题：P3403 跳楼机

给定$x,y,z \leq 10^5,h\leq 2^{63}-1$，求解$a_0x+a_1y+a_2z,0 \leq a_i$
在$[1,h]$的可能取值个数。

只考虑$a_1y+a_2z$的情况，定义$d_i$为前者式子得到的最小的数$p$，使得$p \equiv i ~(\bmod~ x)$。

考虑类似差分约束的建图情况，对于$i$建边：

addedge(i,(i+y)%x,y)
addedge(i,(i+z)%x,z)

跑一次最短路即可。

根据前面的定义,设$d_i=p$，故可以产生贡献：

$\frac{h-d_i}{x}+1$

对$x$的剩余系计算贡献即可(注意$1$也算可达)。

最好选择最小的数作为$x$，使得空间最小。

接着就可以来鞭尸了：[国家集训队]墨墨的等式