โปรแกรม Python คำนวณผลรวมค่าในเซลล์ Hyperrectangle ด้วย GCD

Hyperrectangle (หรือ n-orthotope) คือรูปทรงสี่เหลี่ยมมิติ k โดยแต่ละมิติมีความยาว n₁, n₂, ..., nₖ เซลล์แต่ละเซลล์มีที่อยู่ (p, q, r, ...) และเก็บค่าเท่ากับ GCD (Greatest Common Divisor) ของพิกัด: gcd(p, q, r, ...) โดย 1 ≤ p ≤ n₁, 1 ≤ q ≤ n₂, ฯลฯ

โจทย์: หาผลรวมค่าทุกเซลล์ modulo 10⁹+7

ตัวอย่าง

• Input: [[2, 2], [5, 5]] (2 Hyperrectangles: 2×2 และ 5×5)
• Output: [5, 37]

Hyperrectangle 2×2:

Coordinates & GCD:
(1,1): gcd=1  (1,2): gcd=1
(2,1): gcd=1  (2,2): gcd=2
Sum = 1+1+1+2 = 5

Hyperrectangle 5×5:

Row sums of GCD:
Row 1: 1+1+1+1+1 = 5
Row 2: 1+2+1+2+1 = 7
Row 3: 1+1+3+1+1 = 7
Row 4: 1+2+1+4+1 = 9
Row 5: 1+1+1+1+5 = 9
Total = 5+7+7+9+9 = 37

อัลกอริธึม: Inclusion-Exclusion Principle (หลักการรวม-ตัดออก)

แทนที่จะคำนวณ GCD ทุกเซลล์ (ช้าเมื่อมิติ/ขนาดใหญ่) ใช้หลักการนับ:

กำหนด f(d) = จำนวนเซลล์ที่พิกัดทุกตัวหารด้วย d ลงตัว = ∏⌊nᵢ/d⌋

ผลรวม GCD = Σ d × g(d) โดย g(d) = จำนวนเซลล์ที่ GCD = d อย่างแน่นอน

คำนวณ g(d) จาก f(d) ด้วย Möbius Inversion / Inclusion-Exclusion:

g(d) = f(d) - Σ g(kd) สำหรับ k ≥ 2

โค้ด Python (Optimized)

def solve_hyperrectangle_gcd_sum(input_arr):
    """
    input_arr: List of hyperrectangles, each is list of dimensions [n1, n2, ..., nk]
    returns: List of sums modulo 1_000_000_007
    """
    MOD = 1_000_000_007
    results = []
    
    for dims in input_arr:
        min_dim = min(dims)
        # f[d] = จำนวนเซลล์ที่ทุกพิกัดหารด้วย d ลงตัว
        f = [0] * (min_dim + 1)
        for d in range(1, min_dim + 1):
            prod = 1
            for n in dims:
                prod = (prod * (n // d)) % MOD
            f[d] = prod
        
        # g[d] = จำนวนเซลล์ที่ GCD = d อย่างแน่นอน (Inclusion-Exclusion)
        g = [0] * (min_dim + 1)
        for d in range(min_dim, 0, -1):
            g[d] = f[d]
            # ลบ g[kd] สำหรับ k >= 2
            k = 2
            while k * d <= min_dim:
                g[d] = (g[d] - g[k * d]) % MOD
                k += 1
        
        # ผลรวม = Σ d * g[d]
        total = sum((d * g[d]) % MOD for d in range(1, min_dim + 1)) % MOD
        results.append(total)
    
    return results

# ทดสอบ
input_arr = [[2, 2], [5, 5]]
print(solve_hyperrectangle_gcd_sum(input_arr))  # [5, 37]

# ทดสอบเพิ่มเติม
print(solve_hyperrectangle_gcd_sum([[3, 3, 3]]))  # 3D Cube 3×3×3
print(solve_hyperrectangle_gcd_sum([[10, 10]]))   # 10×10

การวิเคราะห์ Complexity

• Time: O(min_dim × k) ต่อ Hyperrectangle โดย k = จำนวนมิติ
• Space: O(min_dim)
• ดีกว่าวิธี Brute Force O(∏nᵢ) มากเมื่อมิติ/ขนาดใหญ่

การทดสอบเพิ่มเติม

# ทดสอบความถูกต้องกับ Brute Force (ขนาดเล็ก)
def brute_force(dims):
    from math import gcd
    from functools import reduce
    import itertools
    total = 0
    ranges = [range(1, n+1) for n in dims]
    for coords in itertools.product(*ranges):
        total += reduce(gcd, coords)
    return total

# ทดสอบ
test_cases = [[2,2], [3,3], [4,4], [2,3], [3,4], [2,2,2]]
for tc in test_cases:
    fast = solve_hyperrectangle_gcd_sum([tc])[0]
    brute = brute_force(tc) % 1_000_000_007
    print(f"{tc}: Fast={fast}, Brute={brute}, Match={fast==brute}")

การประยุกต์ใช้

• ปัญหาคณิตศาสตร์เชิงจำนวน론 (Number Theory)
• การวิเคราะห์ลวดลาย/รูปแบบในมิติสูง
• Cryptography และ Coding Theory