17425 약수의 합 (node.js)

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

문제

두 자연수 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)를 출력한다.

====

문제 설명

N이 1 이라면 1의 약수는 1 -> f(1) = 1 -> g(1) = f(1) = 1 

N이 2라면 2의 약수는 1, 2 -> f(2) = 1+2=3 -> g(2) = f(1)+f(2) = 1+3 

N이 3라면 3의 약수는 1, 3 -> f(3) = 1+3=4 -> g(2) = f(1)+f(2)+f(3) = 1+3+4 

g(n) 은 f(1)+f(2)+....+f(n-1)+f(n)

즉 g(n) = g(n-1) + f(n) 이 된다.

오답노트 

처음에는 N의 범위가 1부터 1_000_000 이어서, 범위 내의 모든 수의 약수의 합을 구했다.

그 뒤 G라는 배열을 만들어서 G[k] = G[k-1] + (현재 k의 약수의 합)  을 넣어줌.

k의 약수의 합을 구하기 위해 에라스토테네스의 체를 활용하여 2부터 루트(k)까지의 수중 k를 나눴을 때 나머지가 0인 것들을 찾음

const gcd = (n) => {
    if (typeof n !== 'number') return;
    let s = 1 + n; //약수 중 1과 자기 자신

    const pivot = Math.floor(Math.sqrt(n));
    for (let i = 2; i <= pivot; i++) {
        if (n % i === 0) {
            const a = n / i;
            s += i;
            if (a !== i) s += n / i;   // a와 i가 똑같으면 한 번만 약수에 포함되는 조건
        }
    }
    G[n] = s + G[n - 1];
};

 위의 함수를 사용해서 1부터 1_000_000까지 돌린다면 성능으로 아래와 같이 1400~1500ms 가 나온다.

문제에서 요구하는 제한 시간은 1초이므로 이 로직으로 해결이 안된다.

========

내가 생각한 로직에서 문제가 되는 부분은 1부터 1백만수를 검토하면서 그 안에서 또 1부터 루트k까지 찾다보니 중복된 경우가 많았다.

각 수의 약수를 매번 찾는 대신 어떠한 수의 배수를 찾고 해당 배수에 값을 더하는 것이 중복을 줄일 수 있다.

이것을 코드화 하면 

const F = Array.from({ length: MAX + 1 }, () => 1);
F[0] = 0;

for (let i = 2; i <= MAX; i++) {
    for (let j = 1; i * j <= MAX; j++) {
        F[i * j] += i;
    }
}

위 로직대로 F의 모든 수를 구하면 6~10ms가 나온다.

이 F 배열을 활용하여 위에수 구한 G 배열을 구하면

const G = Array.from({ length: MAX + 1 });
G[0] = 0;
for (let i = 1; i <= MAX; i++) {
    G[i] = G[i - 1] + F[i];
}

 

정답 코드 

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

parseInt(input.shift());

const m = input.map((s) => +s);

MAX = 1_000_000;



const F = Array.from({ length: MAX + 1 }, () => 1);
F[0] = 0;

for (let i = 2; i <= MAX; i++) {
    for (let j = 1; i * j <= MAX; j++) {
        F[i * j] += i;
    }
}

const G = Array.from({ length: MAX + 1 });
G[0] = 0;
for (let i = 1; i <= MAX; i++) {
    G[i] = G[i - 1] + F[i];
}

m.forEach((b) => {
    console.log(G[b]);
});

const answer = [];
m.forEach((b) => {
    answer.push(G[b]);
});

console.log(answer.join('\n'));

* 참고로 forEach에서 매번 정답을 출력하지 않고 한번에 출력하는 이유는 console.log가 동기적 I/O 작업으로, 각 로그마다 시스템 리소스를 많이 소모하기 때문에 위처럼 작성해야 시간초과가 뜨지 않는다