【Python】超直方体の全セルGCD値の総和を求めるプログラムと効率的な解法

問題の概要

「超直方体（ハイパーレクタングル）」とは、長方形をk次元へ拡張した図形のことです。各次元の長さは n1, n2, n3, …, nm のように表され、超直方体を構成する各セルは座標 (p, q, r, …) で指定できます。そして、それぞれのセルには gcd(p, q, r, …)、つまりその座標値すべての最大公約数に等しい値が格納されています。

ここでの制約は 1 ≤ p ≤ n1、1 ≤ q ≤ n2、… となっており、インデックスは1から始まります。この記事の目的は、すべてのセルの値 gcd(p, q, r, …) の総和を求め、その結果を 10^9 + 7 で割った余りとして返すことです。

具体例で理解する

たとえば入力が input_arr = [[2, 2], [5, 5]] の場合、出力は [5, 37] になります。入力には2つのテストケースが含まれており、それぞれの超直方体について総和を計算します。

テストケース1：[2, 2] の場合

これは 2×2 の二次元長方形です。各セルの座標 (p, q) とその値 gcd(p, q) は次のようになります。

(p, q)   値
(1, 1)   gcd(1, 1) = 1
(1, 2)   gcd(1, 2) = 1
(2, 1)   gcd(2, 1) = 1
(2, 2)   gcd(2, 2) = 2

GCDの総和 = 1 + 1 + 1 + 2 = 5

テストケース2：[5, 5] の場合

こちらは 5×5 の二次元長方形です。行ごとのGCDの和を整理すると、次の表のようになります。

(p, q)                                 gcd(p, q)      行ごとの和
(1, 1) (1, 2) (1, 3) (1, 4) (1, 5)     1 1 1 1 1      5
(2, 1) (2, 2) (2, 3) (2, 4) (2, 5)     1 2 1 2 1      7
(3, 1) (3, 2) (3, 3) (3, 4) (3, 5)     1 1 3 1 1      7
(4, 1) (4, 2) (4, 3) (4, 4) (4, 5)     1 2 1 4 1      9
(5, 1) (5, 2) (5, 3) (5, 4) (5, 5)     1 1 1 1 5      9

GCDの総和 = 5 + 7 + 7 + 9 + 9 = 37

解法のアプローチ

すべてのセルを一つずつ列挙してGCDを計算すると、次元数や各辺の長さが大きくなったときに計算量が爆発してしまいます。そこで役立つのが、「ある整数 i の倍数だけで構成されるセルの個数」を利用した包除原理（差分計算）です。

coeff_find(test_instance, i) は、各次元の長さを i で割った商（切り捨て）の積、すなわち「すべての座標が i の倍数であるようなセルの総数」を返します。この値から、gcd が 2i, 3i, … となるセルの個数を差し引けば、「gcd がちょうど i であるセルの個数」が求まります。大きい i から順に処理することで、必要な値がすべて確定した状態で引き算ができるのがポイントです。

アルゴリズムの手順

• 関数 coeff_find() を定義します。引数は test_instance と i。
  • value := 1
  • test_instance 内の各次元の長さ k に対して：
    • value := value × (k ÷ i) の整数部分（k // i）
  • value を返します。
• メイン関数では以下を実行します。
• output := 新しい空のリスト
• input_arr 内の各 test_instance に対して：
  • min_value := test_instance の最小値
  • total_value := 0
  • temp_dict := 新しい辞書（マップ）
  • i を min_value から 1 まで 1 ずつ減らしながら繰り返し：
    • p := coeff_find(test_instance, i)
    • q := i
    • q ≤ min_value の間、次を繰り返し：
      • q := q + i
      • q が temp_dict に存在するなら：
        • p := p − temp_dict[q]
    • temp_dict[i] := p
    • total_value := total_value + temp_dict[i] × i
  • ループ完了後、output の末尾に total_value mod (10^9 + 7) を追加
• output を返します。

実装例

それでは、上記のアルゴリズムをPythonで実装してみましょう。

def coeff_find(test_instance, i):
    value = 1
    for k in test_instance:
        value *= k // i
    return value

def solve(input_arr):
    output = []
    for test_instance in input_arr:
        min_value = min(test_instance)
        total_value = 0
        temp_dict = {}
        for i in range(min_value, 0, -1):
            p = coeff_find(test_instance, i)
            q = i
            while q <= min_value:
                q += i
                if q in temp_dict:
                    p -= temp_dict[q]
            temp_dict[i] = p
            total_value += temp_dict[i] * i
        output.append(total_value % (10**9 + 7))
    return output

print(solve([[2, 2], [5, 5]]))

入力

[[2, 2], [5, 5]]

出力

[5, 37]

まとめ

このプログラムは、全セルを直接走査することなく、「倍数の個数」と「包除原理」を組み合わせることで、超直方体の全セルGCD値の総和を効率的に求めます。各テストケースの計算量は、最小の辺の長さを N とするとおおよそ O(N log N) 程度に収まるため、比較的大きな入力にも対応できます。「GCDの総和」を求める問題は競技プログラミングでも頻出のテーマなので、この定番テクニックはぜひ押さえておきましょう。