問題の説明

長方形の紙があり、幅はWcm、長さはHcmです.紙には水平方向と垂直方向に平行なグリッド線があり、すべてのグリッドは1 cm x 1 cmの大きさです.1 cm(グリッドに沿って)× 1センチの正方形に切るつもりだったが、この紙を2つの対角線の頂点を結ぶ方向に切った人がいた.したがって、現在の矩形紙は、同じ大きさの2つの直角三角形に分かれています.新しい用紙が見つからないため、この用紙の横方向と縦方向は元の用紙と平行1 cmである× 1 cmに切って、使えるだけ使ってください.
横方向長さWと縦方向長さHが与えられた場合、使用可能な正方形の個数を求める解法関数を完了する.

せいげんじょうけん

ワット、H:1億以下の自然水

I/O例

WH812

I/O例説明

I/O例#1
幅8、奥行き12の長方形を対角線方向に切り取ると、合計16個の正方形が使用できません.元の長方形は96個の正方形を作成することができ、96～16=80を返します.

ハーモニー

def solution(w,h):
    gcd_value = 0

    # (1)
    for i in range(min(w, h), 0, -1):
        if w % i == 0 and h % i == 0:
            gcd_value = i
            break
   
    answer = (w * h) - (w + h - gcd_value)

    return answer

w = 12
h = 8
print(solution(w,h)) # 결과 예 : 80 

(1):ユークリッドアーク除去法によりw,hの最大公約数を求める

📝 結果

😃 に感銘を与える

この問題は,問題説明によって数学式が導出できる問題であり,数学式が導出できなければ解きにくい.私もこの公式を導き出すことができなかったので、グーグルを通じて「直角三角形内の正常な正方形の個数」の公式を検索しました.この問題は過去に数学オリンピックで提起されました.私のような文系出身は考えることすらできない問題です.

要するに、以上の式は以下の通りです.
(対角線で切り取られた長方形の個数):(横)+(縦)-(横最大公約数)
すなわち、w=8、h=12と入力すると(横最大公約数)=4となる.
(対角線でカットされた矩形の個数)=8+12-4=16.
質問で8、12を出した場合、答えは80です.

次に似たような問題が発生した場合、グーグルを使わずに数学の公式を自分で導き出すように努力しなければならない.頑張れるかどうかは分からないけどね.

公式コメントリンク

👍 Irishのすべてのコードを表示

-> Irish Github