c - 找到两首或多首歌曲交集的算法

Question

假设我们有一堆 radio ，每个 radio 一遍又一遍地循环播放同一首歌曲。是否可以同步所有 radio 中的所有歌曲？我们能找到一个时间从头听到所有歌曲吗？

为了简单起见，我们假设我们只有两个 radio 。

我有以下公式:

c 和 z 代表歌曲的长度，以秒为单位。a 和 x 代表歌曲中的当前位置(以秒为单位)S代表C和Z同步的时间。 (当两首歌同时开始时)

例如:

Song 1
a = 17 : the time before the song ends.
b = 8 : the rest of the song.
c = a + b which is the full song in seconds.
And
Song 2 
x = 8 : the time before the song ends.
y = 9 : the rest of the song.
z = 8 + 9 which is the full song in seconds.

Song 1 : a + ( a + b) => S
Song 2 : x +(( x + y ) × n) => S

Song 1 : 17 + ( 17 + 8) => 42
Song 2 : 8 + ((8 + 9)) = 25
So in order to synchronize song 2 with song 1 we have to multiply (x + y)    
by two and add x to it.

Song 2 : 8 + ((8 + 9) x 2) => 42

So S = 42 and so the two songs will synchronize after 42 seconds.

现在第一个例子是最简单的。对于其他情况，我必须将 z 和 c 乘以 2 以上才能获得适合它们的 S。

我有一些其他的输入，我试图想出一个算法来为我返回 S，但我没有运气。

这是我到目前为止的想法:

c = a + b
a = 16
b = 4
c = 20
s = 216

和

z = x + y
x = 12
y = 5
z = 17
s = 216
S is the LCM of c and z

在第一个示例中，S 是这样找到的:

s = x +(z × n)
n = ( s − x ) ÷ b
12 + ( 17 × 12) = 216

和

s = a + (c × n)
n = ( s − a ) ÷ b
16 + ( 20 × 10 ) = 216

我根据 S 的值得出了下面的两个公式。但是我需要找到一种无需实际使用 S 即可找到 n 的方法。或者换句话说，我需要找出一种方法来找出我应该将 (a + b) 乘以 n 并将 (x + y) 乘以 n 多少次才能得到 S。

n = ( s − a ) ÷ b
S = x + ( y × n)

但是这些公式显然行不通，因为它们需要 S。我们不能使用它，因为那应该是我试图得出的公式的结果。

以下是一些计算的其他示例:

a2 = 52
b2 = 4
c2 = 56
s2 = 276

x2 = 60
y2 = 12
z2 = 72
s2 = 276

这是永远不会同步的情况:

A1 = 14
B1 = 4
C1 = 18
S1 = Never synchronizes

A2 = 19
B2 = 5
C2 = 24
S2 = Never synchronizes

下面是歌曲已经同步的一些情况:

案例一

A2 = 17  
B2 = 0 
C2 = 17 
S4 = 0

A3 = 25  
B3 = 0 
C4 = 25  
S4 = 0

案例二

A4 = 0 
B4 =  13  
C4 = 13  
S4 = 0


A5 = 0 
B5 = 21 
C5 = 21  
S5 = 0

我正在考虑使用最小公倍数，但我不确定在这种情况下如何实现它，或者它是否是解决此问题的正确方法。

如果有超过 2 首歌曲，我想提出的算法也应该有效。例如，为 3 或 4 首歌曲查找 S。

这个算法的主要问题是决定两首歌曲是否同步，计算本身并不难。你能帮我吗 ？提前致谢

Answer 1

c 和z 的最小公倍数是歌曲同步的连续时间间隔(如果它们完全同步)。这意味着，如果我们可以确定一次，我们可以通过添加(或减去)LCM 的倍数来找到其余的。要找到这个时间(实际上是 LCM)，请使用 extended Euclidean algorithm找到满足方程的整数 T, U

 (c - a) + T*c = (z - x) + U*z

在 V = -U 替换下等同于

 T*c + V*z = (c - a) - (z - x).

详细地，找到c和z的GCD，检查它划分(c - a) - (z - x) ，然后将 Bézout 系数乘以 ((c - a) - (z - x))/GCD(c, z)。