找出超矩形单元格中值的总和的 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]

有两个实例作为输入提供给我们，我们必须确定这两个给定实例的总和。在每个实例中，超矩形都是 4x4 的二维矩形，并且给出了长度。地址 (p,q) 和gcd(p,q)将是这样的 -

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

gcd 的总和 = 1 + 1 + 1 + 2 = 5

在第二种情况下 -

(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

gcd 的总和 = 5 + 7 + 7 + 9 + 9 = 37

示例

让我们看看以下实现以获得更好的理解 -

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]