Chương trình Python tìm tổng giá trị ô trong siêu hình chữ nhật

Siêu hình chữ nhật (hyperrectangle) là hình chữ nhật có k chiều. Mỗi chiều có độ dài n1, n2, ..., nm. Các ô được định chỉ số (p,q,r,...) chứa giá trị bằng gcd(p,q,r,...). Với 1 <= p <= n1, 1 <= q <= n2, ... Tìm tổng giá trị tất cả ô gcd(p,q,r,...). Kết quả modulo 10^9 + 7. Chỉ số từ 1 đến n.

Ví dụ: input_arr = [[2, 2], [5, 5]], kết quả [5, 37].

Giải thuật

1. Hàm coeff_find(test_instance, i): tính tích floor(k/i) cho mọi chiều k
2. Hàm chính solve(input_arr):
   • Với mỗi test_instance:
     • min_value := min(test_instance)
     • total_value := 0, temp_dict := {}
     • For i từ min_value xuống 1:
       • p := coeff_find(test_instance, i)
       • q := i
       • While q <= min_value:
         • q += i
         • Nếu q trong temp_dict: p -= temp_dict[q]
       • temp_dict[i] := p
       • total_value += temp_dict[i] * i
     • Thêm total_value % (10^9+7) vào kết quả

Ví dụ

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]]))

Input

[[2, 2], [5, 5]]

Output

[5, 37]