[codeforces] 1977C. Nikita and LCM

문제 링크

1900이라고 방심했다가 크게 데인 문제입니다... 생각보다 생각하기 어렵더라고요... 더 열심히 연습해야겠습니다.

$1$이상 $10^9$이하의 정수들로 이루어진 길이가 $n$인 배열 $a$가 있습니다. $a$의 부분 배열 중에서 배열의 모든 요소의 최소공배수가 $a$의 요소가 아닌 배열 중 최대 길이를 구하는 문제입니다.

케이스를 나눠서 생각해 보겠습니다.

Case 1) $lcm(a_{1}, ..., a_{n}) > a_{n}$

이건 두말할 필요 없이 $n$을 출력하면 됩니다.

Case 2) $lcm(a_{1}, ..., a_{n}) = a_{n}$

우선 부분 배열에는 $a_{n}$이 있으면 안됩니다. $a_{n}$이 들어가는 순간 최소공배수는 바로 $a_{n}$이 되기 때문입니다. 그래서 저희는 $a_{n}$을 제외하고 부분 배열을 만들어야 합니다.
그리고 어떠한 부분 배열을 만들어도 길이가 $0$이 아니라면 최소공배수는 $a_{n}$의 약수가 됩니다. 즉, 아래 과정을 통해서 부분 배열의 최대 길이를 찾을 수 있습니다.

1. $ans = 0$으로 설정합니다. 그리고 $a_{n}$의 약수들을 구합니다.
2. $a_{n}$의 약수들을 순회하면서 아래 과정을 반복합니다. (편의상 약수를 $d$라고 하겠습니다.)
   2-1. $a_{1}, ... , a_{n-1}$ 중에서 $a_{i}|d$인 $a_{i}$들의 최소공배수와 갯수를 구합니다. 편의상 최소공배수를 $l$, 갯수를 $cnt$라고 하겠습니다.
   2-2. $l = d$라면 $ans = max(ans, cnt)$로 업데이트 합니다.
3. $ans$를 출력합니다.

위 풀이의 시간복잡도는 $O(n \cdot \max(a_i)^{\frac{1}{3}} \cdot \log{\max(a_i)})$입니다.
$O(\max(a_i)^{\frac{1}{3}})$은 $\leq 10^{9}$을 만족하는 정수 중에서 약수가 가장 많은 정수의 약수의 갯수를 의미합니다. 시간복잡도를 계산할 때 어떻게 해야할지 몰라서 검색을 해보니 $\leq 10^{18}$에서 약수의 갯수가 최대인 정수의 약수의 갯수를 $O(n^{\frac{1}{3}})$로 생각하면 얼추 맞다고 합니다. 물론 이는 정확한 수학적 근거를 통해서 나온 값이 아닌 실제 계산을 통해서 얻어진 추정값인것 같습니다.

여담으로 약수의 갯수와 관련하여 아래와 같은 성질이 있다고 합니다.

$d(n)$은 $n$의 약수의 갯수, $o(f(n))$은 little-o notation입니다.

Divisor function - Wikipedia
Upper bound for number of divisors - Codeforces
1344 maximal divisors - OEIS