N（村数）的居民什么时候再见面？
When will the residents of N (number of villages) meet again?
所以，问题是我遇到的过去编程竞赛论文的一部分。给定一个数字 N，代表城市中心周围的村庄数量，第一个村庄的村民每 x1 到几天去城市购买他们的物资，第二个村庄的村民每 x2 天等。所有村民都遇到了今天在市中心。我们被要求找出至少 N-1 个村庄的村民什么时候会在同一天再次访问市中心！
示例：
示例 1：
输入 1: 1 2 3 4 5 6 7 8 9 10 -> 输出:360 7
在上面的例子中，除了第7个村的村民之外，所有村民都会在360天后再次见面。
示例 2：
INPUT: 10 14 15 30 21 5 40 4 8 -> OUTPUT: 840 0 (所有村民会再次见面840 天）。
示例 3：
INPUT:25065 3575 12305 88590 1758 -> OUTPUT: 25845383485350 4（所以在 25845383485350 之后除了第 4 个村民之外的所有村民村里再相会。
有没有不用递归的解决方法？谢谢！
你的问题本质上是最小公倍数。 （如果一个城市的村民每5天来一次，他们在第0天来过一次，他们还会在第5、10、15、20天来一次……那显然是倍数。）
因此，解决这个问题的一个好方法是拆分素数中的数字，并且每个素数使用找到的最大效力。
以例2为例：
10, 14, 15, 30, 21, 5, 40, 4, 8 = 2*5, 2*7, 3*5, 2*3*5, 3*7, 5 2^3* 5、2^2、2^3
-> 取最大效力：2^3*3*5*7 = 840
如果你把问题改成有偏移量("the villagers of village 1 were in the city 10 tens ago")，顺便说一句，你可以使用中国剩余定理。
编辑：
至于N-1个村庄的变体，就这样吧：
再次构建质数因子，但这一次，计算哪个质数的效能被找到的频率。再次创建最大效力，然后遍历村庄以查看忽略该特定村庄的村庄需要多长时间才能相遇。有了效能计数，你就可以很容易地看到移除村庄的效果。
我认为知道这个想法就足以编写代码，但如果您需要我详细说明，请直接说。
详细说明：
对于每个素数，存储发现频率的效力。
以例2为例：
10, 14, 15, 30, 21, 5, 40, 4, 8 = 2*5, 2*7, 3*5, 2*3*5, 3*7, 5 2^3* 5、2^2、2^3
- 对于 10 = 2*5，我们存储：
- 2 的效力为 1 (x1)
5 的效力为 1 (x1)
对于 14 = 2*7，我们更新为：
- 2 的效力为 1 (x2)
- 5 的效力为 1 (x1)
- 7 的效力为 1 (x1)
-> 最后：
- 2 的效力为 1 (x3)、2 (x1)、3 (x2)
- 3 的效力为 1 (x3)
- 5 的效力为 1 (x5)
- 7 的效力为 1 (x2)
现在我们再次遍历整个列表，如果只找到一次，则取出当前的效力，然后查看它们的乘积。我们保留该产品的最低数量。
我们用整个产品初始化最小值，在本例中为 840。
- 我们计算 10 = 2*5。 2 的效能 1 和 5 的效能 1 都只找到一次，所以乘积保持 840。
- 除 2 的效力 2 外，所有其他数字均如此，如 4 = 2^2
- 但是因为我们也有 2 的 3 效能，所以这无关紧要，我们仍然使用 840。
让我们自己做个例子：72、74、75 和 296 = 2^3*3^2 2*37 3*5^2 和 2^3*37
->
- 2 的效力为 1 (x1)、3 (x2)
- 3 的效力为 2 (x1)、5 (x1)
- 5 的效力为 2 (x1)
- 37 的效力为 1 (x2)
直到所有村庄再次相会，我们还要等(2^3)(3^5)(5^2)*37 = 1798200天
- 如果我们去掉 72，我们会失去一个 2 的 3 和 3 的 2。第一个无关紧要，因为它存在不止一次，第二个也是，因为有更高的 3 ( ^5).
- 如果我们去掉74，同样成立
- 然而，如果我们取出 75，我们发现它的效力为 2 of 5 是单数，我们可以将其取出。 (2^3)*(3^5)*37 = 71928，这是我们新的最小值
- 296 再次无关紧要，因为 2^3 被发现两次，37^1 也被发现。
因此，我们得到 N-1 个村庄的下一次聚会是在 71928 天之后，除了 75 个以外的所有人都在场。
有帮助吗？
所以，问题是我遇到的过去编程竞赛论文的一部分。给定一个数字 N，代表城市中心周围的村庄数量，第一个村庄的村民每 x1 到几天去城市购买他们的物资，第二个村庄的村民每 x2 天等。所有村民都遇到了今天在市中心。我们被要求找出至少 N-1 个村庄的村民什么时候会在同一天再次访问市中心！
示例：
示例 1：
输入 1: 1 2 3 4 5 6 7 8 9 10 -> 输出:360 7 在上面的例子中，除了第7个村的村民之外，所有村民都会在360天后再次见面。
示例 2：
INPUT: 10 14 15 30 21 5 40 4 8 -> OUTPUT: 840 0 (所有村民会再次见面840 天）。
示例 3：
INPUT:25065 3575 12305 88590 1758 -> OUTPUT: 25845383485350 4（所以在 25845383485350 之后除了第 4 个村民之外的所有村民村里再相会。
有没有不用递归的解决方法？谢谢！
你的问题本质上是最小公倍数。 （如果一个城市的村民每5天来一次，他们在第0天来过一次，他们还会在第5、10、15、20天来一次……那显然是倍数。）
因此，解决这个问题的一个好方法是拆分素数中的数字，并且每个素数使用找到的最大效力。
以例2为例：
10, 14, 15, 30, 21, 5, 40, 4, 8 = 2*5, 2*7, 3*5, 2*3*5, 3*7, 5 2^3* 5、2^2、2^3
-> 取最大效力：2^3*3*5*7 = 840
如果你把问题改成有偏移量("the villagers of village 1 were in the city 10 tens ago")，顺便说一句，你可以使用中国剩余定理。
编辑：
至于N-1个村庄的变体，就这样吧：
再次构建质数因子，但这一次，计算哪个质数的效能被找到的频率。再次创建最大效力，然后遍历村庄以查看忽略该特定村庄的村庄需要多长时间才能相遇。有了效能计数，你就可以很容易地看到移除村庄的效果。
我认为知道这个想法就足以编写代码，但如果您需要我详细说明，请直接说。
详细说明：
对于每个素数，存储发现频率的效力。
以例2为例：
10, 14, 15, 30, 21, 5, 40, 4, 8 = 2*5, 2*7, 3*5, 2*3*5, 3*7, 5 2^3* 5、2^2、2^3
- 对于 10 = 2*5，我们存储：
- 2 的效力为 1 (x1)
5 的效力为 1 (x1)
对于 14 = 2*7，我们更新为：
- 2 的效力为 1 (x2)
- 5 的效力为 1 (x1)
- 7 的效力为 1 (x1)
-> 最后：
- 2 的效力为 1 (x3)、2 (x1)、3 (x2)
- 3 的效力为 1 (x3)
- 5 的效力为 1 (x5)
- 7 的效力为 1 (x2)
现在我们再次遍历整个列表，如果只找到一次，则取出当前的效力，然后查看它们的乘积。我们保留该产品的最低数量。
我们用整个产品初始化最小值，在本例中为 840。
- 我们计算 10 = 2*5。 2 的效能 1 和 5 的效能 1 都只找到一次，所以乘积保持 840。
- 除 2 的效力 2 外，所有其他数字均如此，如 4 = 2^2
- 但是因为我们也有 2 的 3 效能，所以这无关紧要，我们仍然使用 840。
让我们自己做个例子：72、74、75 和 296 = 2^3*3^2 2*37 3*5^2 和 2^3*37
->
- 2 的效力为 1 (x1)、3 (x2)
- 3 的效力为 2 (x1)、5 (x1)
- 5 的效力为 2 (x1)
- 37 的效力为 1 (x2)
直到所有村庄再次相会，我们还要等(2^3)(3^5)(5^2)*37 = 1798200天
- 如果我们去掉 72，我们会失去一个 2 的 3 和 3 的 2。第一个无关紧要，因为它存在不止一次，第二个也是，因为有更高的 3 ( ^5).
- 如果我们去掉74，同样成立
- 然而，如果我们取出 75，我们发现它的效力为 2 of 5 是单数，我们可以将其取出。 (2^3)*(3^5)*37 = 71928，这是我们新的最小值
- 296 再次无关紧要，因为 2^3 被发现两次，37^1 也被发现。
因此，我们得到 N-1 个村庄的下一次聚会是在 71928 天之后，除了 75 个以外的所有人都在场。
有帮助吗？