c++ - 仅使用其他两个数字达到目标数字

Question

我有两个数字 L 和 R，L 表示左，R 表示右。我必须使用 L 和 R 达到某个数字 (F)。每次我都必须从零开始。

例子:大号:1右:2女:3

所以到达 F 所需的最少步数是 3。答案:第一个 R，第二个 R，第三个 L。

在这种情况下，我需要找到最少的方法。

My approach:

Quo = F/R;
Remain : F%R;

x*R-Y*L = Remain
==> (x*R - Remain)/L = Y
this equation is break when (x*R - Remain)%L = 0, so we find x and y from the equation above.
So final Steps would be Quo + x(No. of right steps) + y( no. of left steps).

For Above Example :
Quo = 3/2 = 1;
Remain = 3%2 =1;

Y = (x*2 -1)/1
(x*2 -1)%1 is zero for x=1;
Now increase x from zero,

So x is 1, y is 1

Final Ans = Quo (1) + x (1) + y(1) = 3.

我的代码:

#include <iostream>
using namespace  std;

int main()
{
        int F,R,L;
        cin >> F;
        cin >> R;
        cin >> L;

        int remain = F%R;
        int quo = F/R;

        int Right = 0;
        int left = 0;
        int mode = 1;
        while( mode !=0)
        {
            Right++;
         mode = (R*Right - remain)%L;
         left = (R*Right - remain)/L;

        }
        int final = quo + Right + left;
        cout << final;
}

但我不认为这是一个好方法，因为我将 x 放入循环中，这可能会非常昂贵

你能给我一个做这道题的好方法吗？

Answer 1

在下面给出的等式中

 x*R - Remain = 0modL
 where R, L and Remain are fixed.

可以写成

((x*R)mod L - Remain mod L) mod L = 0

如果 Remain mod L = 0，则 x*R 应该是 L 的倍数，这使得 x 为 0modL。意味着 x 可以是 0，nR 其中 n 是整数。

因此，很简单，您可以尝试在 0 和 L-1 之间寻找 x 以找到 x。

因此，您的循环可以从 0 运行到 L-1，这将使您的循环保持有限。

请注意，此模组与 % 不同。 -1 mod L = L-1 而 -1%L = -1

还有另一种方法。

x*R mod L - Remain mod L = 0 mod L

导致

x*R mod L = Remain mod L
(x* (R mod L)) mod L = (Remain mod L)

您可以在 L 的字段(如果存在)中计算 R 的倒数(比如 Rinv)并计算 x = (Remain*Rinv)modL。如果逆不存在，则说明方程不成立。

注意:我不是数学专家。所以，如果有什么不对的地方，请发表你的意见。

参见:https://www.cs.cmu.edu/~adamchik/21-127/lectures/congruences_print.pdf