[C++]Summer/Winter Coding(2019)멀쩡한 사각형

using namespace std;
 
long long solution(int w, int h)
{
    if (w == h)
        return (long long)w * (long long)h - (long long)w;
 
    long long gcd = 0;
    long long small = 0;
    if (w >= h)
        small = h;
    else
        small = w;
 
    for (long long i = 1; i <= small; ++i)
    {
        if (w % i == 0 && h % i == 0)
            gcd = i;
    }
 
    return (long long)w * (long long)h - ((long long)w + (long long)h - gcd);
}
 

처음에는 그냥 음 라인에 걸리는 것만 하면 되려나 했는데 생각보다 더 쉬웠다...

걸리는 사각형들을 보면 2 x 3 박스 안에 4개씩 걸리는데

이 2 x 3 박스가 8 x 12 내에 4개가 들어있다.

즉 ( 2 x 4 ) x ( 3 x 4 ) 두 수의 최대공약수를 구한다면 더 쉬워진다.

모든 직사각형을 구하고 해당하는 직사각형들(x축, y축의 길이만큼)을 빼고

그만큼 최대 공약수( 2x3박스 수)를 더해주면 된다.

 

하지만 더 간단한 것

( 처음에 말한 것에 반대로 걸리지 않는 것들을 다 구하는 것 )

long long solution(int w, int h) {
    long long answer = 0;
 
    for (int i = 0; i < w; ++i) {
        answer += (int)((double)h*i/w);
    }
 
    return 2 * answer;
}