126. 长方体层(Cuboid Layers)

"""Project Euler 126 - Cuboid Layers."""

from time import perf_counter


def count_layers(max_n: int):
    """Count C(n) for all n from 1 to max_n via direct enumeration.

    Iterates over a <= b <= c and k >= 1, computing L(a,b,c,k) and
    incrementing the count for that value.

    Args:
        max_n: Maximum layer-cube count to consider.

    Returns:
        List C of length max_n+1 where C[n] = count of (a,b,c,k) producing n.
    """
    C = [0] * (max_n + 1)

    # a <= sqrt(max_n / 2) because 2ab <= L for any k >= 1, b >= a
    max_a = int((max_n / 2) ** 0.5) + 1

    for a in range(1, max_a + 1):
        a2 = a * a
        half_n = max_n / 2

        # For fixed a, minimum L occurs when b=c and k=1:
        #   L_min = 2ab + 2b(a+b) = 4ab + 2b^2 <= max_n
        #   => b <= -a + sqrt(a^2 + max_n/2)
        max_b = int(-a + (a2 + half_n) ** 0.5) + 1
        if max_b < a:
            continue

        for b in range(a, max_b + 1):
            ab = a * b
            s_ab = a + b  # a + b

            # For k=1: L = 2ab + 2c(a+b) <= max_n
            #   => c <= (max_n/2 - ab) / (a+b)
            max_c = (max_n // 2 - ab) // s_ab
            if max_c < b:
                continue

            for c in range(b, max_c + 1):
                s_abc = s_ab + c  # a + b + c

                # L for k=1
                L = 2 * (ab + b * c + a * c)
                if L > max_n:
                    continue
                C[L] += 1

                # For k >= 2: L(k) = L(k-1) + 4(a+b+c) + 8(k-2)
                # First increment (k=1 -> k=2): inc = 4(a+b+c)
                inc = 4 * s_abc
                while True:
                    L += inc
                    if L > max_n:
                        break
                    C[L] += 1
                    inc += 8  # each subsequent step adds 8 more

    return C


def solve(target: int = 1000) -> int:
    """Find the smallest n such that C(n) equals the target value.

    Uses iterative deepening with a geometric progression on the search bound.

    Args:
        target: The desired value of C(n). Default 1000.

    Returns:
        The smallest positive integer n for which C(n) == target.

    Raises:
        RuntimeError: If not found within a reasonable bound.
    """
    max_n = 5000
    while max_n < 10 ** 8:
        print(f"Searching up to n = {max_n}...")
        C = count_layers(max_n)

        for n in range(1, max_n + 1):
            if C[n] == target:
                return n

        max_n *= 2

    raise RuntimeError("Not found within search bound")


def verify_samples():
    """Verify C(n) values for the sample data given in the problem."""
    C = count_layers(200)
    samples = {22: 2, 46: 4, 78: 5, 118: 8, 154: 10}
    for n, expected in samples.items():
        actual = C[n]
        status = "PASS" if actual == expected else f"FAIL (got {actual})"
        print(f"  C({n}) = {actual}  {status}")


if __name__ == "__main__":
    t0 = perf_counter()

    print("Sample verification:")
    verify_samples()

    print()
    result = solve(1000)
    elapsed = perf_counter() - t0
    print(f"\nAnswer: {result}")
    print(f"Time: {elapsed:.3f}s")