[programmers][월간 코드 챌린지 시즌2] 약수의 개수와 덧셈

문제 : https://programmers.co.kr/learn/courses/30/lessons/77884

---

left, right가 최대 1000개므로 그냥 1부터 right까지 수들을 탐색하면서 탐색 중인 수가 left ~ right 의 약수인지 2중 for문을 돌려가며 판단한다. 약수의 수를 저장해야 하므로 right-left+1 크기의 배열도 필요하다.

탐색이 모두 끝나면 left~right들의 약수 개수가 짝수면 더하고 홀수면 뺀 결과를 반환한다.

 

시간복잡도는 O(right * (right-left+1)).

---

더 좋은 방법이 있을거 같아서 고민하다가 공식 풀이에 들어가서 지니어스한 방법을 알게되었다.

중요 아이디어는 약수가 홀수개란 뜻은 25와 같이 제곱수라는 뜻이다.

따라서 left ~ right 의 합을 등차 수열 합 공식 n ( a + l ) /  2  (n = 수들의 갯수, a = 첫 번째 수, l = 마지막 수)을 이용해서 O(1) 만에 구하고, 1(또는 루트(left)) ~ 루트(right) 만큼 수들을 탐색(let, 탐색 중인 수 = num) 하면서 num^2 가 left ~ right 사이 수라면 num ^ 2 를 2번 빼준다. 2번 빼주는 이유는 예를 들어, left = 21, right = 26이라면 num = 5일 때, num^2 인 25가 left, right 사이 수라 빼줘야 하는 데 이전에 등차수열 합 공식에 의해 21 + 22 + 23 + 24 + 25 + 26 로 한 번 더 해 졌으므로 2번 빼줘서 21 + 22 + 23 + 24 - 25 + 26 마이너스로 만들어주기 위함이다.

시간복잡도는 O(log right).수학 공식 다른건 모르겠는데 등차수열 합 공식은 엄청 유용하게 잘 쓰고 있다.

---

소스코드 

약수의 개수와 덧셈.cpp

약수의 개수와 덧셈(faster).cpp