백준 11691 lcm(i,j) : lcm과 gcd의 관계를 이용한 역발상이 필요하다.

 오늘은 2019년 마지막 날이니, 마지막 날을 장식할 만한 포스트를 작성하도록 하겠습니다. 아래 수식의 결과 값을 10억 7로 나눈 나머지는 얼마일까요?

 단, n은 2이상, 10^6 이하 자연수입니다. n = 10^6이면 대충 O(n)이나, O(128n)에 돌려도 무난할 복잡도입니다. 이것이 생각보다 꽤 큰 힌트 중 하나입니다.

 

 

---

 먼저, 최대 공약수에 대한 관점을 비틀어 봅시다. a와 b의 최대 공약수가 g였다고 해 봅시다. 이걸 P라고 합시다.

 

 그러면 위 수식이 성립합니다. 그런데 정말 그럴까요? 위 수식을 Q라고 해 봅시다. 만약에, gcd(a/g,b/g)의 값이 c이고, 이 값이 1이 아니라면, gcd(a,b)의 값은 gc가 됩니다. c가 1이 아니므로, gc의 값은 g가 아닙니다. 즉, not Q이면 not P가 참이므로, P이면 Q인 게 참입니다.

 

 이 관계는 나중에 써 먹어 보도록 합시다.

 

 

---

 아래 문제2는 다소 쉽습니다.

 

 

이것과, 원본 문제가 무슨 상관 관계가 있길래 그런 것일까요? 일단, 이 의문에 대한 것은 잠깐 접어두고, 이것 먼저 풀어봅시다.

 

 

 여기서 노란색으로 칠한 것은 제일 왼쪽 열에 있는 것과 서로소인 수를 나타냅니다. 아. 이것도 조금 복잡해 보이네요. 그러면 문제를 n개로 쪼개 봅시다. 먼저, Q(1)의 값은 0입니다. 이건 구하기 쉬우니까 Q(2)부터 봅시다.

 

 

2번째 문제는 [1,2] 범위에 속하는 수들 중, 2와 서로소인 수들의 합을 구한 다음에 이것을 2와 곱하는 것입니다. 이것을 Q(2)라 합시다.

 

 

 3번째 문제는 [1,3] 범위에 속하는 수들 중, 3과 서로소인 수들의 합을 구한 다음에 이것을 3과 곱하는 것입니다. 이것을 간략하게 Q(3)이라 합시다.

 

 

 그러면 문제 Q(n)은 다음과 동치입니다. n과 서로소인 수들의 합을 모두 구한 후에, n과 곱한 결과값을 계산한다. 그러면 문제2는 Q(1) + ... + Q(n)을 구하는 것과 동치라는 것을 간파하셨으리라 생각이 됩니다. 일반화를 시켜 봅시다. k와 서로소이려면, k의 소인수들의 배수가 아니여야 합니다. k의 소인수가 2, 3, 5라고 한다면, 2의 배수가 아니고, 3의 배수도 아니고 5의 배수도 아니여야 합니다. 즉, 2의 배수거나, 3의 배수거나, 5의 배수의 여사건입니다.

 

 2의 배수이거나, 3의 배수이거나, 5의 배수이거나. 이것은 포함 배제의 원리로 접근하실 수 있습니다. 2의 배수이면서 3의 배수이면 6의 배수인 경우의 수를 구하면 되고요. 그러면 구간 [1,n]에서, u의 배수들의 합은 어떻게 구하면 될까요?

 

 

 n = 5이고, u = 2라고 해 봅시다. 그렇다면, [1, 5] 구간에서 u의 배수는 2, 4일 겁니다. 몫이 1, 2인 것만 있는 셈입니다. 몫이 floor(5/2)인 것까지 있다는 겁니다. 1부터 a까지의 자연수들을 모두 더한 것의 합은 a(a+1)/2로 구할 수 있습니다. 그러면 구간 [1,n]에서 k의 배수들의 합 또한 일반화 시켜서 구할 수 있을 거에요.

 

 몫이 floor(n/k)인 것까지 있어요. 1부터. floor(n/k)를 t라고 한다면, k(1+...+t)의 값을 구하면 되므로, k(t(t+1)/2)의 값만 잘 구하면 됩니다.

 

 

 제가 설명한 Q(x) 문제를 구현한 함수가 calc(x)입니다.

 

 

 그러면 문제2는 어떻게 풀면 될까요? 0<a<b<n+1에 대해서, gcd(a,b)의 값이 1인 ab 곱들의 합은 Q(1) + ... + Q(n)을 구하면 되므로, 20번째 줄과 같이 처리하면 됩니다.

 

 

---

 그런데, 이것은 gcd(a,b) = 1인 경우만 처리했지, gcd(a,b) = k인 경우에는 처리하지 않았습니다. 예를 들어 gcd(a,b) = 2인 경우라던지, gcd(a,b) = 15인 경우라던지 등등. 일단, 왜 하필 최소 공배수를 구해야 하는데, 최대 공약수에 신경을 쓸까요?

 

 이 수식 때문에 그런 걸까요? 아닙니다.

 

 

 위에서 언급한 이 명제 때문입니다. 우리는 0<a<b<K에 대해, gcd(a,b) = 1인 ab 곱들의 합을 구했습니다. 이 명제를 이용하면 어떻게 바뀌는지 잘 봅시다.

 

 

 예를 들어, 0<a<b<5이면서 gcd(a,b) = 2인 모든 쌍 (a,b)에 대해, lcm(a,b)의 합을 구한다고 해 봅시다. 위 예제에서는 (4, 2)만 있으므로, lcm의 합은 4입니다.

 

 그런데 이건 사실 맵을 가로로 1/2, 세로로 1/2만큼 쪼개 놓은 것에서 gcd(a,b) = 1인 모든 쌍 (a,b)에 대해 ab의 합을 구한 다음에 2를 곱한 것과 같습니다. 이걸 일반화 시켜 봅시다.

 

 

 0<a<b<n+1을 만족하면서 gcd(a,b) = k인 쌍 (a,b)에 대해서 lcm(a,b)의 합들을 구하라 했어요. 그러면 먼저, 맵을 가로로 1/k, 세로로 1/k배율 쪼개놓고 출발해 봅시다. 그러면 gcd(a/g, b/g)는 1이기 때문에, g에다가, 0<a<b<floor(n/k)+1을 만족하면서, gcd(a,b) = 1인 쌍 (a,b)에 대해서 ab의 곱의 합을 곱하는 문제로 바뀌어 버립니다. 그런데, 노란색 형광펜으로 칠한 부분은 이미 구해 놓았습니다. 그 값은 이미, dp에 저장이 되어 있어요.

 

 

 그러므로, 그냥 꺼내 쓰면 됩니다. 문제에서 설명한 것을 모두 구현한 코드는 링크에 있습니다.