https://gall.dcinside.com/m/ps/32003

너무 쉬운 문제인데 질문해도 되나..이게 문제고이렇게 하면 되겠다! 싶었지만..뭔가 이상함.. 뭐가 문제일까요..?문법 방금 막 배우고 문제 처음 접해보는거라많이 서툴러요.. 죄송합니다gall.dcinside.com



https://www.acmicpc.net/problem/26056

Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net


1. 가장 나이브한 접근법


S부터 T까지의 수 중 하나를 x라 하자.

모든 x에 대해 1부터 x까지 나누어보고 약수임이 확인 되면 (-1)^(i)를 더해준다(i는 x의 약수).


이 방식은 최악의 경우 O(N^2)로 너무 오래 걸린다.




2. 두번째로 나이브한 접근법


우린 12의 약수를 구할 때,

1 * 12

2 * 6

3 * 4

이렇게, 1부터 12까지 나누지 않고, sqrt(12)까지 나누는 걸로 모든 약수를 구해본 적이 있다.


그러므로 S부터 T까지의 수 중 하나를 x라 하면,

모든 x에 대해 1부터 sqrt(x)까지 나누어보고 약수임이 확인 되면 (-1)^(i)와 (-1)^(x/i)를 더해주는 걸로 구할 수 있다(i는 x의 약수).


근데 이래도 O(N*sqrt(N))이라 너무 오래 걸린다.




3. 배수를 이용하는 접근법


S부터 T까지의 a_i 합은 1~T까지의 a_i 합에서 1~(S-1)까지의 a_i 합을 빼는 식으로 구할 수 있다.

그럼 1부터 N까지의 a_i 합을 구하는 방법을 고민해보자.

이때 우리는 약수의 개수를 구하는 것보다 배수의 개수를 구하는 게 더 간단하다는 사실을 이용할 수 있다.


어떤 수 x의 약수의 개수를 구하는데는 O(sqrt(x))만큼의 계산이 필요하지만,

1부터 N까지의 수 중 어떤 수 x의 배수의 개수(x를 약수로 갖는 수의 개수)는 N/x에 해당하는 값으로 O(1) 만에 구할 수 있다.


그렇다.

우린 1부터 N까지 돌면서 배수의 개수를 세는 식으로 a_i 합을 구할 수 있다.


1를 약수로 갖는 수는 N/1개

2를 약수로 갖는 수는 N/2개

.

.

.

N을 약수로 갖는 수는 N/N개 이므로

(N)*(-1)^1 + (N/2)*(-1)^2 + ... + (N/N)*(-1)^N을 계산하는 걸로 1부터 N까지의 a_i 합을 구할 수 있다.


근데 이 방법조차도 O(N) 시간이 걸려서 시간 초과가 난다.

여기서 시간을 더 줄일 수 있는 방법이 있다.

바로 2번에서 시간복잡도를 줄였던 아이디어를 가져오는 것이다.




4. O(sqrt(N)) 알고리즘


우리가 1부터 N까지의 a_i 합을 구하면서 x를 약수로 갖는 자연수의 개수 N/x를 구할 때,

우린 반대쪽 약수의 개수도 세어 줄 수 있다.


이제는 약수로 갖는 자연수를 계산해줄 때 반대쪽 약수도 함께 계산해줄 것이다.


1부터 N까지의 수 중 1을 약수로 갖는 자연수 개수를 구할 때,

1 * 1

1 * 2

1 * 3

.

.

.

1 * N/1

이렇게 표현할 수 있는데,

이 과정에서 1이 N번 쓰인 사실을 아는 것뿐 아니라 2, 3, 4, ... N도 쓰인 사실을 알 수 있다(1 * 1에서 오른쪽 1은 중복이므로 제외).

따라서 왼쪽 값 N*(-1)^1을 더하고 오른쪽 값 (-1)^2 + (-1)^3 + ... + (-1)^N을 더해준다.


2를 약수로 갖는 자연수 개수 역시

2 * 1

2 * 2

2 * 3

.

.

.

2 * N/2 에서

왼쪽 값 2를 더할 때, 2 * 1은 1 * 2에서 이미 계산한 값이므로 빼면, (N/2 - 1) * (-1)^2를 더할 수 있다.

오른쪽 값은 2 * 1은 이미 계산한 값, 2 * 2는 왼쪽 값을 계산할 때 계산했으므로 (-1)^3 + (-1)^4 + ... + (-1)^(N/2)를 더해준다.


이걸 1부터 sqrt(N)까지 반복하면 1부터 N까지의 a_i합을 구할 수 있다.

sqrt(N) 이후의 값은 이미 계산한 값에 해당하므로 계산하지 않아도 된다.

그리고 위 값을 계산할 때, 오른쪽 값은 연속되는 홀짝의 값 (-1)^(2k) + (-1)^(2k+1)이 0이므로 시작 수와 끝 수의 홀짝 여부로 모두 더하지 않고 구할 수 있다.

따라서, 이 방식대로면 1부터 N까지의 a_i 합을 O(sqrt(N))의 시간복잡도로 구할 수 있다.