BOJ 15744, USACO 2018 Feb P3 Cow Gymnasts

• 풀이 : 관찰
• 풀이 : 시간 복잡도 줄이기
• 풀이 : 더 고통받기

출처 : USACO 2018 February Platinum Problem 3 - Cow Gymnasts (BOJ 15744)
난이도 : solved.ac Diamond 3
문제 링크

풀이 : 관찰

DHdroid가 ‘재밌는 문제’ 라면서 들고왔습니다. 나름 재밌게 풀었는데 후반에 좀 허탈했습니다.

• 먼저, $N$개의 자리를 통틀어 최소값이 $m$ 이라고 하고, 그 최솟값이 있는 자리를 $k$번이라고 합시다.
• $k - 1, k - 2, \dots k - m + 1$ 번 까지는 어쩔 수 없이 $k$번에 Contribute합니다.
• $k-m$번은 $k$번에 Contribute해서는 안 되므로, 값이 정확히 $m$이여야 합니다.
• 이와 같은 논증을 귀납적으로 반복하면, 다음 조건을 만족하는 조합이 ‘성공하는 조합’ 임을 알 수 있습니다.
  • 먼저 최솟값 $m$에 대해 주기 $\gcd(m, N)$ 을 갖고,
  • 각 주기 내에서의 값은 $m$ 또는 $m+1$ 이어야 합니다.
• 따라서, 다음 식을 계산하는 것으로 끝납니다. \(1 + \sum_{i = 1}^{N - 1} \left(2^{\gcd(i, N)} - 1\right)\) 이 관찰을 하는 것까지만이었으면 아마도 플래티넘 정도의 문제였을 것입니다.

풀이 : 시간 복잡도 줄이기

$N = 10^{12}$ 이기 때문에, 이 식을 시간 내에 단순하게는 계산할 수 없습니다.
앞의 잡다한 부분은 떼고 $\sum_{i = 1}^{N} 2^{\gcd(i, N)}$ 을 빠르게 계산하는 방법에 대해 생각해 보겠습니다.

먼저, $\gcd(i, N) = g$ 인 $i \leq N$의 개수를 빠르게 셀 수 있습니다.

• $i$는 $g$의 배수여야 하므로 $i = gk$ 라고 쓰면, $\gcd(k, N/g)$ 이 1이어야 하며
• $k < N / g$ 여야 합니다.
• 따라서, 이러한 $k$는 정확히 $\phi(N / g)$ 개 있고, 다음 식을 계산하면 됩니다. \(\sum_{g \di N} 2^g \phi(N / g)\)
• $g \di N$ 을 모두 구하는 것은 $O(\sqrt{N})$ 시간이 걸리며, $g$가 몇 개 있는지는 정확히 쓰기 매우 어렵습니다.
  • 다만, PS에서 일반적으로 쓰는 바운드는 $O(n^{1/3})$ 입니다. 재밌는 사실은, 이 바운드는 수학적으로 찾은 바운드가 아니라, $10^{9}$ 까지의 수들 중 약수가 가장 많은 수가 1,344개, $10^{18}$ 까지의 수들 중 가장 많은 수가 103,680개의 약수를 갖기 때문에 대충 저만큼 잡으면 된다는 것이 알려져 있다는 점입니다.
  • $O(n^{1/3})$ 개의 약수 각각 $\phi(g)$ 를 구하는 시간은 조금 빡빡합니다. 구체적으로는 개당 $O(n^{1/2})$ 시간인데
  • 실제로는 $g$들 중 상당수가 $N$에 비해 많이 작기 때문에, $O(n^{1/3})$개의 약수에 대해 각각 $\phi$함수를 구하는 풀이는 시간 제한을 통과합니다.
• 더 최적화하는 방법은, $\phi$ 함수는 그 수의 소인수분해 형태에 의해 정해지며, $N$의 소인수는 많아야 수십 개 선이라는 점입니다.
• 각각의 $g \di N$ 은 $N$의 소인수의 부분집합을 갖기 때문에, $p_1^{e_1} p_2^{e_2} p_3^{e_3}\dots$ 에 대해 각 소인수의 개수를 iterate하면 빠르게 구할 수 있습니다.
• 잘 짜면 $O(n^{1/2} \log n)$ 에 구할 수 있다고 합니다.

풀이 : 더 고통받기

• 저는 저 식으로 통과할 자신이 없었기 때문에, 뭔가 새로운 아이디어를 찾아야 한다고 생각했습니다.
• Identity function $\iota$, Mobius function $\mu$ 에 대해, $\phi = \mu * \iota$ 임이 알려져 있습니다. (디리클레 합성곱)
• $f(n) = 2^n$ 을 $p$ 함수라고 하면, 우리의 문제는 $p * \phi$ 의 값을 구하는 것이므로, $p * \mu * \iota$ 를 구하는 것이고
• 다시 이를 $\mu * (p * \iota)$ 로 바꾸어 계산할 수 있습니다.

처참하게도, $\mu$를 계산하기 위해 포함-배제의 원리를 이용해야 하기 때문에 시간 복잡도는 전혀 줄어들지 않고 $\log$ 항이 하나 더 붙습니다 (뫼비우스 함수의 값을 모두 계산하는게 아니라서, map 같은 자료구조를 이용해야 하기 때문. 심지어 결과적으로 이 풀이는 위 풀이의 $O(n^{5/6}))$ 보다도 훨씬 느렸습니다. 간신히 시간 제한을 통과할 수 있었습니다. :(