Python程序找出超矩形单元格中值的总和

Python程序找出超矩形单元格中值的总和

超矩形是一个具有k个维度的矩形。每个维度的长度可以表示为n1、n2、n3…..nm。超矩形的单元格被标识为(p、q、r、……)并且包含一个等于(p、q、r、……)的最大公约数的值。其中1≤p≤n1,1≤q≤n1等。我们的任务是确定所有单元格值gcd(p、q、r、……)的总和。结果以模10^9 + 7返回。索引从1到n,且总和≤10^15。

因此,如果输入为[[2,2],[5,5]],则输出将为[5,37]。

有两个实例作为输入,并且我们必须确定这两个给定实例的总和。在每个实例中,超矩形是4×4的二维矩形,长度已知。地址(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。

在第二个实例中−

(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。

要解决此问题,我们将遵循以下步骤−

  • 定义函数coeff_find()。这将采用test_instance和i。
    • value := 1
    • 对于test_instance中的每个k,执行以下操作
      • value := value * (k / i)的值
    • 返回value
  • 从主方法/函数中,执行以下操作−
  • 输出:=一个新的列表
  • 对于input_arr中的每个test_instance,执行以下操作
    • min_value := test_instance中的最小值
    • total_value := 0
    • temp_dict := 一个新的map
    • 对于i从min_value到0的范围,递减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 % (10**9 + 7)
  • 返回output

示例

以下是更好的理解实现的实例−

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]

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程