C++(코딩테스트) - 멀쩡한 사각형

이 문제는 수학 문제와 관련이 많고

어떤 규칙이 있을지 살펴보다가

서로소인경우 w+h-1인것을 알게되었다.

이후 못쓰는 사각형 조건 2가지를 발견하였고

1. if (w == 1 || h == 1) return 0;

2. 최대공배수 * (w*h/최대공배수 -1)

전체 사각형의 수 w*h 에서 빼주면 된다.

참고로 (long long)w * h 안해주면 값이 초과되어 실패가 될 수 있다.

 

int gcd(int a, int b) { return (a % b == 0 ? b : gcd(b, a % b)); }

long long solution(int w, int h) {
	long long answer = 1;

	if (w == 1 || h == 1)
	{
		return 0;
	}

	int a = gcd(w, h);
	answer = ((long long)w * (long long)h) - (w / a + h / a - 1) * a;

	return answer;
}