[프로그래머스]멀쩡한 사각형

내 풀이 : 좌표마다 계산

시간복잡도에서는 선형적이지만, 그래도 직관적인 풀이 같다.

function solution(w, h) {
    var answer = 1;
    var big = h>w?h:w
    var small = h>w?w:h
    var cnt=0;
    for(var i=0;i<small;i++)
{
   cnt += (Math.ceil((i+1)*big/small)-Math.floor(i*big/small))
}
    return w*h-cnt
}

 다른 사람 풀이 : 최대 공약수 활용

w*h - (w+h-gcd(w,h))

왜 이렇게 되는 것일까!

예를 3,5라면, 결국에 옆으로 3칸 밑으로 5칸을 가야된다. 따라서 w+h-gcd(w,h)인가,,?