資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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。
因此，如果輸入類似於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
最大公約數之和 = 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
最大公約數之和 = 5 + 7 + 7 + 9 + 9 = 37
為了解決這個問題，我們將遵循以下步驟：
定義一個函式coeff_find()。這將接收test_instance和i作為引數
- value := 1
- 對於test_instance中的每個k，執行：
- value := value * (k / i) 的浮點值
- 返回value
- 從主方法/函式執行以下操作：
- output := 一個新的列表
- 對於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時，執行：
- q := q + i
- 如果temp_dict中存在q，則：
- 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
示例
讓我們看看以下實現以獲得更好的理解：
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]
更新於: 2021年5月18日
140次瀏覽
廣告