먼저, [1, N] 안에서 x의 배수들의 합을 s(x; N)이라고 하면,
s(x; N) = 1x + 2x + ... + floor(N/x)*x
= x(1 + 2 + ... + floor(N/x))
= x(floor(N/x) * (floor(N/x) + 1) / 2)
floor(N/x)는 O(1) 안에 구할 수 있으므로 s(x)는 O(1)
문제의 답을 구하는 함수를 S({n_k}; N)이라고 하면, 포함배제의 원리에 의해
S({n_k}) = sum{0<i<=n}{s(n_i)} - sum{0<i<j<=n}{s(lcm(n_i, n_j))} + sum{0<i<j<k<=n}{s(lcm(...))} - ...
lcm({a_n})은 O(1)에 구할 수 있다(원래는 O(n)이지만 여기서는 다음 lcm을 구할 때마다 전 계산값을 써서 계산 중복을 줄일 수 있다)
그러므로 S({n_k}) 안에서 s(x)가 불린 횟수는
(k, 1) + (k, 2) + ... + (k, k) = 2^k ((n, k) 는 조합)
그러므로 S({n_k}; N) 는 O(2^k)에 구할 수 있다
아침에 그 파이썬 %3 %5 보고서 이 문제 생각했는데 나도 2^k에서 안 줄더라
a_k가 모두 prime이고 N이 저 prime들의 곱의 배수면 이항정리써서 O(k)까진 나오거든 근데 N이 거기서 좀만 벗어나도 완전 달라짐
걍 1부터 N까지 돌면서 각 수가 k개의 정수중 하나의 배수인가? 를 구하면 Nk로 풀 수 있는거 아님? 2^k보다 Nk가 더 저렴한거 아닌가?
이건 둘이 비교 못함. O(Nk)는 N = k 이면 O(k^2) 고 N = 2^k 면 O(k*2^k) 임
간단하게 N을 k번째 소수까지 곱/2 같은걸 생각해봐 난리남