正如標題所說，我需要一種演算法來找到最小整數 m ，當除以 n 個不同的整數時會留下不同的余數。
我知道 m 必須至少為 n 并且這樣的 m 總是存在（m = max（所有整數） 1），但我不明白如何繼續找到最小的 m。任何幫助表示贊賞！
謝謝
uj5u.com熱心網友回復：
最快的方法就是嘗試一下。
def distribute_remainders (numbers):
m = len(numbers)
while True:
is_used = set()
for x in numbers:
if x % m in is_used:
break
else:
is_used.add(x % m)
if len(numbers) == len(is_used):
return m
else:
m = 1
測驗給定數字的余數需要O(n). 平均而言，它只需要log(n)嘗試，直到你遇到一個肯定會起作用的素數。因此，平均而言，這并不比O(n log(n))而且可能更好。
最壞的情況呢？https://primes.utm.edu/notes/gaps.html表示，下一個素數的保證上限仍在改進中，但最好的記錄在O(n^0.535). 所以最壞的情況是O(n^1.535)并且可能更接近O(n^1.5)。
相比之下，如果我們試圖變得聰明，就會發現有O(n^2)差距。因此，在我們列舉它們之前，我們比極不可能的最壞情況做得更糟。
uj5u.com熱心網友回復：
如果我們想象串列已排序，我們會發現彼此之間有不同距離的數字：
a b c d e f...
<---> <--> ...
<--------> <-------> ...
<---------> ...
...
要復制余數，其中一個距離必須是m或 的倍數m。
一種可能的解決方案是從m2 開始；并創建一組所有距離的所有除數，m每次其中一個除數匹配時遞增 1。
例如，
[2, 6, 8, 14]
m = 2
Distance Divisors m
4 4, 2 3
6 6, 2, 3 5
12 12, 6, 3, 2 5
2 2 5
8 8, 4, 2 5
6 6, 2, 3 5
Remainders mod 5:
[2, 1, 3, 4]
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/492027.html