[Baekjoon] 17425 약수의 합(자바스크립트/NodeJs)

이번 문제는 아래 링크에서 풀어볼 수 있습니다.

17427번: 약수의 합 2

---

🤔 문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다.

예제 입력 1

5
1
2
10
70
10000

예제 출력 1

1
4
87
4065
82256014

---

정답 코드

답안1

---

문제 풀이

 단순 for 반복문으로 문제를 풀면 시간초과가 뜬다. 따라서 N = AB일 때 N은 A와 B의 배수라는 성질을 이용해서 풀어야 한다. 

f(y): 자연수 A의 모든 약수를 더한 값
// i의 배수에 해당하는 인덱스에 i 더함.
[ 1, 3, 4, 7, 6, 12, 8, 15, 13, 18 ...]

g(x): x 이하 모든 자연수 y의 f(y)값을 더한 값들
// 누적값 계산 answer[i] += answer[i - 1]; 실행 후 
[ 1, 4, 8, 15, 21, 33, 41, 56, 69, 87 ...]

 숫자 6을 예로 들어보자. 숫자 6의 약수는 [1, 2, 3, 6]이다. 위의 f(y) 배열에서 6번째 값은 12이다. 이는 숫자 6의 모든 약수를 합한 값과 같다. 즉 이중 for 반복문을 돌면서 i의 배수에 해당하는 인덱스 j에 i 값을 더해나가는 것이다. 이 같은 작업을 마친 후 앞선 요소의 값들을 누적시킨다. 입력 받은 숫자를 인덱스로 활용하면 num 이하 모든 자연수 y의 모든 약수 합을 구할 수 있다.

---

함께 보기

https://lhoiktiv.tistory.com/414

Node.js) 백준 17425번: 약수의 합

https://enhjh.tistory.com/38

[백준/수학] 17425 약수의 합(Python, 파이썬)

https://velog.io/@jswon/%EB%B0%B1%EC%A4%80-17425-%EC%95%BD%EC%88%98%EC%9D%98-%ED%95%A9-python

백준 17425 약수의 합 - python