Lv 2ユークリッドアーク除去法、GCD、LCM完全矩形C++

1692 ワード
programmers GCD LCM algorithm テキストリンク
注意-ユークリッドアーク除去法
  • ・(12 x 8)の長方形から切り取ったパターンが形を繰り返しているので、この形が何回繰り返されているか見てみましょう
  • 切り取られた図形が見える外接矩形(3 X 2)の矩形총 4번繰り返し
  • これは12와 8의 최대공약수 4各値を除く3,2
  • および外接矩形から実際に切り取った矩形はw*h-1個
    • ここでは,最大承諾数を求めるために,ユークリッドアーク除算を用いる.

    📍Euclideanアルゴリズム(注:ウィキペディア)

  • 2個の自然数a,bについて、aをbで割った残りをr(a>b)と呼ぶ
  • aとbの最大承諾数がbとrの最大承諾数に等しい
  • この性質からbをrの残りr「で割って、rで割って」と求める過程が繰り返される
  • 剰余が0の場合、数aとbで割った最大公約数

    • 📍Greatest Common Divisor (GCD)

    public static int gcd(int a, int b) {
	while (b>0) {
    	int tmp=b;
        b=a%b;
        a=tmp;
    }
    return a;
}

    📍Least Common Multiple (LCM)

    public static int lcm(int a, int b) {
	return (a*b) / gcd (a,b);
}

    📝Source Code

    using namespace std;

int getGCD(int a, int b) {
	while (b>0) {
    	int tmp=b;
        b=a%b;
        a=tmp;
    }
    return a;
}

long long solution(int w,int h) {
    long long answer = 1;
   
    int gcd=getGCD(w,h);
    int mw=w/gcd;
    int mh=h/gcd;
  
    long long cut=(long long)mw+mh-1;
    cut*=gcd;
   
    answer=(long long)w*h-cut;
   
    return answer;
}
    MyBaseコード
    22、23強:ヒップ(Heaps)