Python程式：查詢N個自然數中和能被k整除的數對數量

假設我們有一個數字n和另一個值k，考慮我們有一個數組A，其中包含前N個自然數，我們需要找到陣列A中元素A[i]和A[j]的所有對的數量，滿足i < j且它們的和能被k整除。

因此，如果輸入類似於n = 10，k = 4，則輸出將為10，因為有10對的和能被4整除。[(1,3), (1,7), (2,6), (2,10), (3,5), (3,9), (4,8), (5,7), (6,10), (7,9)]

為了解決這個問題，我們將遵循以下步驟：

  • m := n / k的向下取整，r := n mod k
  • b := 一個新的對映
  • 對於i從0到k - 1，執行以下操作：
    • b[i] := m
  • 對於i從m*k+1到n，執行以下操作：
    • j := i mod k
    • b[j] := b[j] + 1
  • c := 0
  • 對於i從0到k，執行以下操作：
    • i1 := i
    • i2 :=(k - i) mod k
    • 如果i1等於i2，則
      • c := c + b[i] *(b[i]-1)
    • 否則，
      • c := c + b[i1] *(b[i2])
  • 返回c/2的向下取整

示例

讓我們看看以下實現，以便更好地理解：

def solve(n, k):
   m = n // k
   r = n % k

   b = {}
   for i in range(k) :
      b[i] = m
   for i in range(m*k+1, n+1) :
      j = i % k
      b[j] = b[j] + 1

   c = 0
   for i in range(k) :
      i1 = i
      i2 = (k - i) % k
      if i1 == i2 :
         c = c + b[i] * (b[i]-1)
      else :
         c = c + b[i1] * (b[i2])
   return c//2

n = 10
k = 4
print(solve(n, k))

輸入

4, 27

輸出

10

更新於： 2021年10月25日

213 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告