멀쩡한 사각형 C++

문제설명

제한사항

• W, H : 1억 이하의 자연수

입출력 예

W                                                       H                                                                 result

8

12

80

입출력 예 설명

입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

 

 

 

=> 가려지는 사각형들은 그룹핑을 할 수 있습니다. 

=> 가려지는 사각형들의 무리는 W와 H의 최대공약수의 갯수만큼 있습니다. 

=> 작은사각형무리에서 지워지는 사각형의 갯수는  X+Y-1입니다. (X:W를 최대공약수로 나눈수 Y:H를 최대공약수로 나눈수)

=> 나머지는 아래의 풀이를 보면 됩니다. 

 

 

 

#include <algorithm>
#include <vector> 
#include <iostream>

using namespace std;
int gcd(long long a, long long b)
{
    long long c;
    while(b!=0)
    {
        c= a%b;
        a=b;
        b=c;
    }
    return a;
}
long long solution(int w,int h) {
    long long answer = 1;
    answer =(long)w * (long)h;
    answer = answer -(w+h-gcd(w, h));
    
    return answer;
}