【Python】最初のN個の自然数から合計がkで割り切れるペアの数を求めるプログラム

問題の概要

数 n と値 k が与えられ、最初の N 個の自然数(1, 2, ..., n)を要素とする配列 A があるとします。このとき、i < j を満たす要素 A[i] と A[j] のペアのうち、その合計が k で割り切れるものの総数を求めるのが課題です。

例えば、入力が 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)]

解法のアプローチ

この問題は、全ペアを素朴に調べる O(n²) の方法よりも、各数を k で割った余りに注目することで大幅に効率化できます。2つの数の合計が k で割り切れるのは、それぞれの余りの和が 0 または k になる場合だからです。

具体的な手順は以下の通りです。

• m に n ÷ k の商(小数点以下切り捨て)、r に n を k で割った余りを設定します。
• 新しいマップ(辞書)b を作成します。
• i が 0 から k - 1 までの範囲で、b[i] に m を代入します(各余りクラスの基本個数)。
• i が m×k + 1 から n までの範囲で、j = i mod k として、b[j] を 1 ずつ増やします(端数分の調整)。
• カウンター c を 0 で初期化します。
• i が 0 から k - 1 までの範囲で、i1 = i、i2 = (k - i) mod k とします。i1 と i2 が等しい場合(自己補完となる余り)、c に b[i] × (b[i] - 1) を加算し、異なる場合は c に b[i1] × b[i2] を加算します。
• 最後に c ÷ 2 の切り捨て値を返します(各ペアが2回カウントされるため半分にします)。

実装例

理解を深めるために、実際の Python コードを見てみましょう。

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

入力

n = 10, k = 4

出力

10

まとめ

この手法では、余りごとの個数を集計してから組み合わせを計算するため、計算量は O(n + k) となり、n が大きい場合でも高速に動作します。余り 0 どうし、および余りが k/2 となる数同士(偶数の k の場合)は同一グループ内での組み合わせ C(b, 2) を用い、それ以外の余りは相補的な関係(b[i] と b[k-i])を掛け合わせることでペア数を求めている点がポイントです。