超直方体セルの値の合計を見つけるPythonプログラム

超直方体は、k次元の長方形です。各次元の長さは、n1、n2、n3、.....、nmで表すことができます。超直方体のセルは（p、q、r、...）としてアドレス指定され、（p、q、r、...）のgcdと同等の値が含まれています。ここで、1 <=p <=n1、1 <=q<=n1などです。私たちのタスクは、すべてのセル値gcd（p、q、r、...）の合計を決定することです。結果はモジュロ10^9+7として返されます。インデックス付けは1からnまで行われます。

したがって、入力がinput_arr =[[2、2]、[5、5]]のようである場合、出力は[5、37]

入力として与えられた2つのインスタンスがあり、これら2つの与えられたインスタンスの合計を決定する必要があります。いずれの場合も、超直方体は4x4の2次元長方形であり、長さが指定されています。アドレス（p、q）とgcd（p、q）は次のようになります-

(p,q)   value   gcd(p,q)
(1, 1)  (1, 2)  1 1
(2, 1)  (2, 2)  1 2

gcdsの合計=1+ 1 + 1 + 2 =5

2番目の例では-

(p,q)  value                gcd(p,q) sum(gcd of row i)
(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

gcdsの合計=5+ 7 + 7 + 9 + 9 =37

これを解決するには、次の手順に従います-

• 関数coeff_find（）を定義します。これにはtest_instanceが必要です。i

  • 値：=1
  • test_instanceのkごとに、
    • value：=value *（k / i）のfloat値
  • 戻り値
• メインのメソッド/関数から、次の手順を実行します-
• 出力：=新しいリスト
• input_arrのtest_instanceごとに、
  • min_value：=test_instanceの最小値
  • total_value：=0
  • temp_dict：=新しいマップ
  • min_valueから0の範囲のiの場合、1ずつ減らします。
    • p：=coeff_find（test_instance、i）
    • q：=i
    • q <=min_valueの間、do
      • q：=q + i
      • qがtemp_dictに存在する場合、
        • p：=p --temp_dict [q]
    • temp_dict [i]：=p
    • total_value：=total_value + temp_dict [i] * i
    • リスト出力の最後に（total_value mod（10 ^ 9 + 7））を追加します
• 出力を返す

例

理解を深めるために、次の実装を見てみましょう-

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]