AtCoder - Cubic Cake -

問題リンク

AtCoder Typical90 V

考え方

幅 ( A )、奥行き ( B )、高さ ( C ) の直方体をすべて立方体にするための最小の立方体の辺の長さは、( A )、( B )、( C ) の最大公約数（GCD）を求め、それを基準に切断すれば良いです。

• 例えば、( A=2, B=2, C=3 ) の場合、最大公約数は 1 なので、全てのピースを ( 1 × 1 × 1 ) の立方体にする必要があります。
• ( A=4, B=4, C=2 ) の場合、最大公約数は 2 なので、全てのピースは ( 2 × 2 × 2 ) の立方体にできます。

解法

1. 直方体の ( A, B, C ) の最大公約数（GCD）を求めます。
2. 各次元を最大公約数で割った値が、その方向に対する切断の回数になります。

コード

import math

def minimum_cuts(A, B, C):
    # A, B, Cの最大公約数を求める
    gcd_length = math.gcd(math.gcd(A, B), C)

    # 各方向で最大公約数の立方体に切るための必要な切断回数
    cuts_A = (A // gcd_length) - 1
    cuts_B = (B // gcd_length) - 1
    cuts_C = (C // gcd_length) - 1

    # 総切断回数は各次元で必要な切断の和
    total_cuts = cuts_A + cuts_B + cuts_C
    return total_cuts

# 入力を受け取る
A, B, C = map(int, input().split())

# 最小の操作回数を出力
print(minimum_cuts(A, B, C))

解説

1. 最大公約数 ( gcd(A,B,C) ) を求めます。
2. 各次元をその最大公約数で割った結果、どれだけ切る必要があるかを計算します。切る回数は、各次元を最大公約数で割った数から 1 を引いたものです。
3. 3つの次元に対する切断回数の合計を出力します。