直方体を一刀で切断！切り分けられたキューブの数を求めるPythonプログラム

問題概要

一辺の長さが a、b、c の単位立方体（キューブ）を組み合わせて、a×b×c の直方体を作ることを考えます。ただし、a、b、c はペアごとに互いに素、すなわち gcd(a, b) = gcd(b, c) = gcd(c, a) = 1 を満たすものとします。

この直方体を、下の図のように頂点 P・Q・R を通る平面でたった一刀で2つに切断します。このとき、断面によって「2つに切り分けられてしまう」単位立方体が何個あるかを求めるのがこの問題です。複数のテストケースが配列として与えられるので、それぞれのケースについて答えを計算して返します。

切断は、頂点 P、Q、R の3点を通る平面によって行われます。

切断されるキューブの数を求める式

頂点 P、Q、R を通る平面で切断したとき、切り分けられるキューブの個数は次の式で一発に求められます。

切断されるキューブ数 = ⌊(a × b + a × c + b × c − 1) ÷ 2⌋ mod 1000000007

a、b、c が互いに素であるため、切断面が内部の格子点を余計に通らず、このシンプルな式だけで正確な個数が得られます。また、答えが巨大になるのを防ぐため、1000000007 で剰余を取っています。

解法の手順

この問題は、以下のステップで解くことができます。

1. 結果を格納するための空リスト output を用意する。
2. i を 0 から n−1 まで繰り返す。
   • a ← input_array[i][0]、b ← input_array[i][1]、c ← input_array[i][2] を代入する。
   • val ← ((a * b + a * c + b * c − 1) // 2) % 1000000007 を計算する。
   • val を output の末尾に追加する。
3. output を返す。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

def solve(n, input_array):
    output = []
    for i in range(n):
        a, b, c = input_array[i][0], input_array[i][1], input_array[i][2]
        val = ((a * b + a * c + b * c - 1) // 2 % 1000000007)
        output.append(val)
    return output

print(solve(3, [[1, 2, 3], [4, 2, 5], [6, 8, 2]]))

入力

3, [[1, 2, 3], [4, 2, 5], [6, 8, 2]]

出力

[5, 18, 37]

出力の解説

3つのケースそれぞれについて、切断されるキューブは 5 個、18 個、37 個です。例えば [4, 2, 5] の場合、(4×2 + 4×5 + 2×5 − 1) ÷ 2 = 37 ÷ 2 = 18.5 となり、小数点以下を切り捨てて 18 が答えになります。同様に [1, 2, 3] では 5、[6, 8, 2] では 37 が求まります。

このように、互いに素な3辺の長さが分かれば、実際に切断をシミュレーションしなくても、ひとつの式だけで切断されるキューブの個数を高速に計算できます。