Siêu hình chữ nhật là hình chữ nhật có k kích thước. Mỗi thứ nguyên có độ dài có thể được ký hiệu là n1, n2, n3, ....., nm. Các ô của siêu hình chữ nhật được đánh địa chỉ là (p, q, r, ...) và chứa giá trị tương đương với gcd của (p, q, r, ...). Ở đây 1 <=p <=n1, 1 <=q <=n1, v.v. Nhiệm vụ của chúng ta là xác định tổng của tất cả các giá trị ô gcd (p, q, r, ...). Kết quả được trả về dưới dạng modulo 10 ^ 9 + 7. Việc lập chỉ mục được thực hiện từ 1 đến n.
Vì vậy, nếu đầu vào giống như input_arr =[[2, 2], [5, 5]], thì đầu ra sẽ là [5, 37]
Có hai trường hợp được cung cấp cho chúng tôi làm đầu vào và chúng tôi phải xác định tổng cho hai trường hợp đã cho này. Trong mỗi trường hợp, các siêu hình chữ nhật là hình chữ nhật 4x4 2 chiều và độ dài được cho trước. Địa chỉ (p, q) và gcd (p, q) sẽ như thế này -
(p,q) value gcd(p,q) (1, 1) (1, 2) 1 1 (2, 1) (2, 2) 1 2
Tổng số gcds =1 + 1 + 1 + 2 =5
Trong trường hợp thứ hai -
(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
Tổng gcds =5 + 7 + 7 + 9 + 9 =37
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàm coeff_find (). Điều này sẽ thực hiện test_instance, tôi
- giá trị:=1
- đối với mỗi k trong test_instance, thực hiện
- giá trị:=value * giá trị float của (k / i)
- giá trị trả về
- Từ phương thức / chức năng chính, hãy thực hiện như sau -
- output:=một danh sách mới
- đối với mỗi test_instance trong input_arr, hãy thực hiện
- min_value:=tối thiểu test_instance
- total_value:=0
- temp_dict:=một bản đồ mới
- đối với tôi trong phạm vi min_value thành 0, giảm đi 1, thực hiện
- p:=coeff_find (test_instance, i)
- q:=i
- while q <=min_value, do
- q:=q + i
- nếu q có trong temp_dict, thì
- p:=p - temp_dict [q]
- temp_dict [i]:=p
- total_value:=total_value + temp_dict [i] * i
- thêm (total_value mod (10 ^ 9 + 7)) vào cuối đầu ra danh sách
- trả về kết quả đầu ra
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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]])) Đầu vào
[[2, 2], [5, 5]]
Đầu ra
[5, 37]