[알고리즘]멀쩡한 사각형

처음 문제를 접하고나서 전혀 규칙을 모르겠어서 찾아봤더니 단위정사각형에서 대각선을 그었을때 지나가는 사각형의 개수는

W+H-(W와H의 최대공약수) 라는 공식이 따로 있다는것을 알았다.

최대공약수는 유클리드 호제법이라고 무슨 공식이 따로 있는것 같지만 나는 쓸줄 모르므로 일단은

각각의 약수를 구하고 중복되는것들중 가장 큰값으로 최대공약수를 구했다

그다음 가로*세로 - (가로+세로-최대공약수)를 계산을 했다.