Chương trình tìm số cặp từ N số tự nhiên có tổng giá trị chia hết cho k trong Python

Giả sử chúng ta có một số n và một giá trị khác k, coi chúng ta có một mảng A với N số tự nhiên đầu tiên, chúng ta phải tìm tổng số các cặp phần tử A [i] và A [j] từ A, sao cho, i

Vì vậy, nếu đầu vào là n =10 k =4, thì đầu ra sẽ là 10 vì có 10 cặp mà tổng của chúng chia hết cho 4. [(1,3), (1,7), (2,6) , (2,10), (3,5), (3,9), (4,8), (5,7), (6,10), (7,9)]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=tầng của (n / k), r:=n mod k
• b:=một bản đồ mới
• đối với tôi trong phạm vi từ 0 đến k - 1, thực hiện
  • b [i]:=m
• đối với tôi trong phạm vi m * k + 1 đến n, thực hiện
  • j:=tôi mod k
  • b [j]:=b [j] + 1
• c:=0
• đối với tôi trong phạm vi từ 0 đến k, thực hiện
  • i1:=i
  • i2:=(k - i) mod k
  • nếu i1 giống với i2, thì
    • c:=c + b [i] * (b [i] -1)
  • nếu không,
    • c:=c + b [i1] * (b [i2])
• tầng trả lại của c / 2

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

4, 27

Đầu ra

10