algorithm - 将 A 转换为 B 所需的最少步骤数

Question

我最近参加了一个编码比赛，其中一个问题如下:

给定两个整数 X 和 Y，找出将 X 转换为 Y 所需的最少步骤数。您可以按任意顺序执行以下操作任意次数:

1) X 除以任意整数 A，2) X 乘以任意整数 B。

示例:如果 X=15 且 Y=10，则首先将 X 乘以 2 得出 30，然后将 30 除以 3 得到 Y(即 10)。所以最低没有。在这种情况下，步骤数为 2。

我不知道如何解决它。

Answer 1

如前所述，最小步数不超过两个:您始终可以选择 A=X 和 B=Y，以便 X/A*B = X/X*Y = Y .

您可以做得更好的唯一时间如下:

如果 X % Y = 0，则最小步数为 1，正确选择为 A=(X/Y)。

如果 Y % X = 0，则最小步数为 1，正确选择为 B=(Y/X)。

如果 X = Y，则最小步数为 0，因为根本不需要乘法或除法。