algorithm - 查找总和为 0 mod n 的数组

Question

有长度为 m 的数组，其中所有条目都是正 (>= 0) 整数。我希望条目的总和为 0 mod n。

我想要一个所有此类数组的列表，其中条目的平方和小于 k。

我该怎么做呢？我想不出找到所有这样的数组的方法，只是其中的一些。

我可以展示我用 python 编写的内容，但是我的方法有缺陷，我需要从头开始，所以除非有人要求，否则我不会展示它。

Answer 1

我现在只能想到一个非常暴力的解决方案。让我举一个实数的例子。让 m = 4，n = 5 和 k = 25。因此，您将拥有的是遍历所有数组并针对每个位置，测试从 1 到给定范围u的所有数字。对于这个u的计算，我想到了这个。在这种最坏的情况下，你会得到类似的东西：

[1 1 1 u]

这意味着 3 + u**2 必须小于 k。因此，我使用u作为 int(sqrt(k - (m-1)))。

from math import sqrt

array = [1, 2, 3, 4]
comb = [0 for i in range(m)]
u = int(sqrt(k-m+1))

all_combs(comb, 0, 0, 0)

def all_combs(comb, pos, sum, square_sum):
    global n, m, u, k

    if (square_sum > k):
        # Invalid case
        return
    if (pos == m):
        if (sum % n == 0):
            print comb
        return

    for i in range(1,u+1):
        comb[pos] = i
        all_combs(comb, pos + 1, sum + i, sum_square + i**2)

清楚吗？

Answer 2

以下是三个可以帮助您的观察结果：

1. 数组上的约束与数组元素的顺序无关。因此假设a_0 <= a_1 <= ... <= a_m-1。

2. 一个[a_0,...,a_m-1]非负整数数组有总和0 mod n当且仅当-a_m-1 = a0 + ... + a_m-2 mod n。因此，第一个m-1条目是免费的，但最后一个条目是固定的。

3. 该条件a_0^2 + ... + a_m-1^2 < k限制了条目的大小。因此循环是有限的。

解决方案可能是这样的：

array := [0,...,0];
sqsum := sum_{j=0..m-1} array[j]^2;
for i := m-2...1 do {
  array[i]++;
  for j from i+1 to m-2 do
    array[j] := array[i];
  L := sum_{j=0..m-2} array[j] mod n;
  array[m-1] := n-L;
  sqsum := sum_{j=0..m-1} array[j]^2;
  while sqsum < k do {
    print(array);
    sqsum := sqsum + 2*array[m-1]n+n^2;
    array[m-1] := array[m-1]+n;
  }
}