Pythonで合計値がkで割り切れるN個の自然数からペアの数を見つけるプログラム

数nと別の値kがあるとすると、最初のN個の自然数を持つ配列Aがあるとすると、Aから要素A[i]とA[j]のペアの総数を見つける必要があります。

したがって、入力がn =10 k =4の場合、合計が4で割り切れる10のペアがあるため、出力は10になります。[（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：=新しい地図
• 0からk-1の範囲のiの場合、do
  • b [i]：=m
• m * k + 1からnの範囲のiについては、
  • j：=i mod k
  • b [j]：=b [j] + 1
• c：=0
• 0からkの範囲のiについては、
  • 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