메모리를 줄이더라도 종이를 직접 구현하는 방법으로는 시간/메모리 초과를 피할 수 없습니다.

힌트는 포함배제의 원리입니다.

전형적인 포함 배제 문제이긴 한데

아마도.. 교집합 연산을 구현하기가 어려우셨으리라 생각이 되는군요.

a의 배수이면서 b의 배수이려면 a와 b의 최소 공배수의 배수여야 겠죠..

그나마 다행인 것은

소인수 분해가 안 나왔다는 것인데요.. 보통 정수쪽에서 포함 배제 냄새가 나는 경우에는..

(제가 백준에서 문제를 푼 경험으로는) 소인수 분해를 착실하게 해야 하는 경우가 많더라고요.

그런 경우에는 문제가 어려워지는데요.

대표적인 예로는 최소 인수라던지. 제곱 ㄴㄴ가 있겠네요. 물론, 이번에 올라온 세 쌍 서로수도 그런 류고요.

포함 배제 자체는 어려운 이론은 아니지만

활용해야 하는 경우가 나오면 극단적으로 어려워지는 경우가 있어요. 조심하셔야 해요..

그런 문제들은 원하신다면

추천해 드리겠습니다. 아주 쉬운 것부터 난이도별로 차근차근 푸실 수 있게..