algorithm - 有几个职位？

Question

我正在练习基于算法的编程问题。我在解决这个问题时遇到了困难。我想要想法(只有小方法/提示)来有效地解决这个问题，所以请帮助我。!这是问题声明::

假设有两只兔子，分别命名为rabbit foo和rabbit bar。最初它们都位于原点(中心)，彼此面对。

Foo 知道只有两个长度 m,n 的跳跃。也就是说，foo 可以向左跳跃 m 长度或向右跳跃 m 长度或向左跳跃 n 长度或向他跳跃 n 长度一次尝试右侧。

同样，bar 也知道只有两个长度的跳跃 - p,q。也就是说 bar 可以跳到他左边的 p 长度或他右边的 p 长度或他左边的 q 长度或他的 q 长度一次尝试右侧。

现在这两只兔子的主人想把自己准确地放在一个点上，这样两只兔子都可以通过一次或多次尝试到达他的主人身边。此外，主人将自己放置在离原点最多 L 的距离处。我们要计算主人可以把自己放在多少位置。

m,n,p,q 和 L 很大，有 10^17。

那么如何高效的解决呢。

示例:

m=1 n=2

m=4 n=5

L=1

answer=3;

作为

Foo 可以向右侧跳 2 个长度，然后向左侧跳 1 个长度。

Bar 可以跳到他的右侧 5 个长度，然后跳到他的左侧 4 个长度。

到达距离原点 1 个单位的主人。

Foo 左边 2 个长度，右边 1 个长度。左边 5 长和右边 5 长的条形到达他的主人，他的主人位于距离原点 1 个长度的地方

Master 也可以将自己放在原点，因为 foo 和 bar 都可以在两步内到达他的 master所以总位置=3。

其他例子:

m=2 n=4

p=3q=6

L=7

answer=3.

m=10 n=12

p=3q=9

answer=5

Answer 1

Foo 可以到达 gcd(m,n) 的倍数的任何位置，而且只能到达这些位置。 bar能到达的位置是gcd(p,q)的倍数，所以两者能到达的位置正好是lcm(gcd(m,n),gcd(p, q)).