【競プロ典型90問】「022 - Cubic Cake（★2）」解法

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。

問題

022 - Cubic Cake（★2）

ポイント

あるピースが立方体であるとは、立方体を形成する全ての辺の長さが同じであることを意味します。

幅A、奥行きB、高さCのケーキを最小回数で立方体に切り分けるには、A,B,Cの最大公約数を求め、

その長さの立方体を切り出せば良いです。

入力例1だと最大公約数は1となるので、操作回数は

　Aを切る回数 + Bを切る回数 + Cを切る回数 = (2 ÷ 1 - 1) + (2 ÷ 1 -1 )+ (3 ÷ 1 - 1 ) = 4回

入力例2だと最大公約数は2となるので、操作回数は

　Aを切る回数 + Bを切る回数 + Cを切る回数 = (2 ÷ 2 - 1) + (2 ÷ 2 -1 )+ (4 ÷ 2 - 1 ) = 1回

となります。

※補足
　ある長さの辺Xからある長さの辺Yを切り分けるときの操作回数は(X ÷ Y - 1)となります。

コード

def main():
    import sys
    import math
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline

    a, b, c = map(int, input().split())
    gcd = math.gcd(c, math.gcd(a, b))
    ans = a // gcd - 1 + b // gcd - 1 + c // gcd - 1
    print(ans)


if __name__ == '__main__':
    main()