查找總和爲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; 
    } 
}