题目

ak47

题意

在数轴上有两个点 A B (给出坐标),还告诉你 a,b

表示可以向左或向右走 a 或 b 或者走 a+b

6种走法 走一次算一步

问从 A 走到 B 最少要多少步。

题解

容易想到方程 ax+by=c

x表示用a走了多少次 y表示用b走了多少次

这样用扩展gcd可以求出一组解和解的取值范围 同时可以判断是否有解(c%gcd(a,b)==0?)

假如x y同号 ans=min(abs(x),ans(y))(因为可以一次走(a+b));异号 ans=abs(x)+abs(y);

x y的取值范围 在直角坐标系上是两条直线 且斜率一正一负 在交点处取最优值

但是交点有可能是小数 那么就枚举交点周围的几个值 取最小值

程序