python math의 lcm 함수에 대해 간단하게 알아봅시다.

 python math의 lcm은 여러 정수의 최소 공배수를 구하기 위한 함수입니다.

 

---

 1번째 예제입니다. 2와 3의 최소공배수를 구하라고 했습니다. 결과는 6이 나올 겁니다. 왜냐하면 2와 3의 공배수 중 최소인 것은 6이기 때문입니다.

 

 여기까지는 별로 어렵지 않습니다. 당연한 것이니까요.

 

 

 이제 0과 5의 최소 공배수를 구하려고 합니다. 어떻게 나올까요? 문서를 찾아보면, 하나라도 0이 있는 경우에 무조건 0이 나온다고 되어 있습니다. 따라서, 이 경우에는 0이 나오게 됩니다.

 

 정말 그리 나오네요. 만약에 음수가 있으면 어떻게 될까요?

 

 

 -4와 6의 최소공배수를 구하려고 합니다. 이 경우, -4의 multiple과 6의 multiple이면서 가장 값이 작은 positive integer를 돌려줍니다. multiple을 조금 더 넓게 볼 필요가 있는데요. y = ax이고, a와 x와 y가 integer라면 y는 x의 multiple이라고 합니다. 12는 -4의 multiple인가요?

 

 네. 왜냐하면 12 = -4에 -3을 곱한 것이기 때문입니다. 그리고, -4, -3은 integer에 속합니다.

 

 고로, -4와 6의 최소 공배수는 12라는 결과가 나옵니다. 여기까지는 쉽게 이해할 만한 내용입니다.

 

---

 제가 출제했던 가희와 서울 지하철 1호선 문제는 구간 lcm을 잘 처리해야 하는 문제였습니다. 그런데, python의 math.lcm을 잘못 사용해서 overflow가 발생했던 경우가 조금 있었습니다. 일단, math.lcm의 경우 결과 값으로 얼마나 커지면 런타임 에러를 뱉어버릴까요?

 

 간단하게 1과 10^9000의 최소공배수를 구해 봅시다.

 

 그랬더니 어떻게 나오나요? 4300자리 수까지 출력 가능하다 되어 있어요. 이 제한을 물론 풀어버릴 수도 있어요.

 

 3.11버전부터 추가된 sys의 set_max_str_digits로 풀어버리면 됩니다. 8번째 줄에 9005라고 넣었는데요. 9005자리의 수까지 제한을 풀어버리겠다는 의미입니다.

 

 그러면 10^9000도 정상적으로 출력됨을 확인할 수 있습니다. 그런데 소수들 몇 개를 lcm 시켜버리면 상당히 큰 수가 나오게 됩니다. 2이상 5000 이하 소수들의 최소 공배수를 구해 보겠습니다. 그리고 제가 해당 문제에서 그러한 데이터를 세팅해 놓지 않았을 리가 없을 겁니다.

 

 어떻게 해야 할까요? 이 문제의 경우, 최대 제한을 넘어가는 경우에 inf로 잘라버리면 됩니다. 예를 들어 1부터 5000까지 최소 공배수를 구해야 한다고 해 보겠습니다. 그러면, inf가 넘어가는 순간에 강제로 최소 공배수가 inf가 되게끔 조정해 주면 됩니다. 우리에게 중요한 정보는 특정 구간의 최소 공배수가 1 이상 100만 이하의 소수이냐입니다. 만약에 최소 공배수가 inf라면 이 범위를 초과하는 것이기 때문에, valid 하지 않다는 정보는 쉽게 파악이 가능합니다.

 

 1부터 5000까지의 최소 공배수는 너무 크니까 1061109567로 처리해도 됩니다. 그렇게 해도 문제에서 요구하는 1 이상 100만 이하의 소수보다는 작습니다. 1061109567이 나왔다는 것은 이미 답이 100만을 초과했다는 것과 동치입니다.