题意:

给你数轴上的两个点X,Y,你有6中走法,分别是从X向各个方向走a个单位、b个单位、(a+b)个单位。求最少要走几步走到Y。

思路:

令步数为T,其中向左走a 个单位p次,b个单位q次(p,q可以为负数)则有:
$$ T=
\begin{cases}
|p|+|q| & \text{pq\textless =0} \\
max(|p|,|q|) & \text{pq\textgreater 0}
\end{cases}
$$
那么我们只需要用扩展欧几里德算法求出p,q的特解p0,q0,再计算什么p,q,可以让T取得最小值。
首先,为了让你走到X,则有:
$$
p_0\times a + q_0\times b = Y-X
$$
由扩展欧几里德算法:
$$
\begin{cases}
p = p_0 + t\times \frac{b}{gcd(a,b)} \\
q = q_0 - t\times \frac{a}{gcd(a,b)}
\end{cases}
$$
所以我们发现p和q都可以表示为关于t的直线,且这两条直线的斜率一正一负,他们必定有一个交点。
所以我们不妨画出这个图像。


其中阴影部分的竖线长度就是T,是不是很直观?
所以我们需要求出这两条线的交点。由于这两条直线不一定橡胶于整点,所以我们需要计算交点及其周围的竖线长度。于是这道题就没了。