[プログラマー]通常の長方形(Python)

質問する

正方形

問題の説明

w,h<=1億であるため,O(wxh)を持つ時間的複雑度はタイムアウトする.初めて思いついたのはw,hの最大公約数を求めてw,hの範囲を縮小して答えを探すことでしたが,2つの数の場合,この方法は通用しないので考えが変わりました.
どう考えても答えがなく、数学の問題だと思って、答えを見つけた.直線カットされた矩形の個数は横(W)＋縦(H)−G(最大公約数)である.実際,最大公約数が2より大きい矩形と相互間の矩形,正方形などを描いて実験を行ったが,カットされた矩形の個数はすべて上記式と同じであった.最後は暗記するしかない.

ソースコード

def GCD(a, b):
    gcd = 1
    small = a if a < b else b
    for i in range(2, small + 1):
        if a % i == 0 and b % i == 0:
            gcd = i
    return gcd

def solution(w,h):
    answer = w * h - (w + h - GCD(w, h))
    return answer