查找总和为0的数组n

Question

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

我想要一个所有这些数组的列的平方和小于k的列表。

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

我可以显示我在Python中编写的内容，但是我的方法有缺陷，我需要从头开始，所以除非请求，否则不会显示它。

Answer 1

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

[111ü]

这意味着，3 + U ** 2必须小于k。因此，我使用int（sqrt（k - （m-1）））作为int（0128）。

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; 
    } 
}