4

我有多个包含多个同余的集合。

在将中国余数定理应用于每组中的一个项目时，我试图找到最小的余数。

以 2 套为例：

设置 1：

7x + 1
7x + 3

第 2 组：

11x
11x + 2
11x + 7
11x + 8

取 7x + 1 & 11x 得到 77x + 22。
我追求最小的余数（在上面的例子中 77x + 8），而不必测试所有组合。

这是我实际问题的非常简化的版本（约 50 组，每组约 100 个同余）。

我被困在如何解决这个问题上，任何建议将不胜感激。

另外，如果我的数学术语不正确，我深表歉意。

4

2 回答 2

2

有一种中间相遇算法，可以及时找到最小的残差

O(max(|S1|, |S2|) log(max(|S1|, |S2|)))。

先用中国剩余定理求S1中满足t mod n1且t mod n2 == 0的所有0 <= t < n1*n2的集合T1和满足t的所有0 <= u < n1*n2的集合T2 mod n1 == 0 和 S2 中的 t mod n2。

即在问题中给出的示例中：

T1 = {22, 66}

T2 = {0, 7, 35, 63}

现在，您正在寻找的残差是总和 (t1 + t2) mod n1*n2，对于 T1 中的任何 t1 和 T2 中的 t2。因此，最小的残差要么是 T1 和 T2 中两个最小元素的总和，要么是刚好大于 n1*n2 的两个元素。如果对集合 T1 和 T2 进行排序，则可以通过从最小元素到最大元素扫描第一个集合并从最大到最小元素扫描最大集合来找到第二种情况的最佳解决方案，即推进 T1 中的位置每当总和小于 n1*n2 时，只要总和大于 n1*n2，就减少 T2 中的位置。

如果你有两个以上的模数 n1 .. nk 那么我能看到的最快的解决方案是将模数分成两组，比如 n1 .. nr 和 nr+1 .. nk 找到集合 T1 使得 t 在 T1 iff t对于所有 1 <= i <= r 和 t mod ni == 0 在 Si 中的 mod ni 对于所有 r < i <= k。相应地定义了 T2。复杂性取决于模数的分布，但通常应该是可能性数量的平方根。Schroeppel 和 Shamir 的算法可以节省一些内存，但不会降低时间复杂度。

对于您的应用程序，即 50 个模数和 100 个全等，此算法仍然使用大约 100^25 步，这是不可行的。不幸的是，看起来没有多项式算法。特别是，已知找到方程 x^2 == a (mod n) 的最小解 x，其中 n 是高度复合整数是 NP 完全的。但是找到这样的解决方案可以减少你的问题。因此，您的问题通常也应该是 NP 完全的，除非同余具有一些可以利用的特殊属性。

于 2011-06-29T22:21:12.837 回答
1

设集合为 S1, S2, ... Sk，其中每个集合中的模数为 n1 > n2 > ... > nk，Si 中的余数为 a_i1 < a_i2 < ... 例如：n1 = 11 , n2 = 7 和 S1 = {0, 2, 7, 8}, S2 = {1,3}

这是一个伪代码：

Find the target modulus, i.e. n = lcm(n1, n2, ..., nk)

Convert the sets Si into hashtables, so that you can check if a certain element is in the set or not.

for (int b = 0; b < n / n1; b++)
    foreach (int c in [a_11, a_12, a_13, ...])
        //candidate target reminder
        a = b*n1 + c
        works = true;
        foreach (int ni in [n2, n3, ..., nk])
           //test if there is an element in Si, which gives the correct reminder
           //if not then this candidate doesn't work, go to the next
           if( not Si contains (a % ni))
               works = false;
               break
        if (works)
            print "The solution is n*x+a"
            exit

这个想法是寻找最小值。如果最小值是 a，那么 a 可以表示为 a=x*n1+y，其中 y 是 S1 中的某个元素，因此我按升序迭代所有可能性。然后对于它们中的每一个，我检查其他集合 - 它们是否包含当前 a 满足的同余。假设第二组 S2：应该存在来自 S2 的同余，例如 p*n2+q，因此对于某个 p，a = p*n2+q。但这意味着 a % n2 = q（因为 q 是余数）。即 % n2 应该在 S2 中。

该算法的复杂度为 O (n/n1 * |S1| * k)。这就是为什么我选择 n1 作为最大模数。但是如果你真的想最小化复杂度，你应该选择集合 Si 使得 n/ni * |Si| 在最小的。

于 2011-06-28T04:13:15.857 回答