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