[백준/17425] 약수의 합

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

 

Difficulty : Gold 4

 

Status : Solved

 

Time : ?? : ?? : ??

 

---

 

문제 설명

 

 

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

 

입력 예시

 

5
1
2
10
70
10000

 

출력 예시

 

1
4
87
4065
82256014

 

 

---

 

풀이

 

관점을 바꾸어 보자. 어떤 수 m의 모든 약수 n을 일일히 찾는 것 보다, 어떤 수 n의 배수 m을 전부 찾아 n을 저장하는 편이 더 빠르다. 약수 판정은 O(Nsqrt(N))이 소모되므로 이런 문제에서는 비효율적이지만, 배수를 찾는 경우는 이보다 더 빠르다.

 

즉 문제 풀이를 요약하면

• 1부터 10^6까지의 모든 수에 대해 배수에 해당하는 index에 그 수를 더하고
• 누적 합을 이용해 g(N) 값을 미리 구한 다음
• 각 쿼리에 대해 저장된 g(N)값을 출력하면 된다.

 

풀이 코드 (Python)

import sys
input = sys.stdin.readline

max = 10 ** 6
fval = [1] * (max + 1)
gval = [0]

def init() :
  for i in range(2, max+1) :
    for j in range(i, max+1, i) :
      fval[j] += i

  for i in range(1, max+1) :
    gval.append(gval[-1] + fval[i])

def query() :
  Q = int(input())
  for _ in range(Q) :
    print(gval[int(input())])

if __name__ == "__main__" :
  init()
  query()

 

풀이 코드 (Go)

package main

import (
	"bufio"
	"fmt"
	"os"
)

const maxVal int = 1000001

var reader *bufio.Reader = bufio.NewReader(os.Stdin)
var writer *bufio.Writer = bufio.NewWriter(os.Stdout)
var fval = [maxVal]int{}
var gval = [maxVal]int{}

func initalize() {
	for i := 1; i < maxVal; i++ {
		for j := i; j < maxVal; j += i {
			fval[j] += i
		}
	}
	for i := 1; i < maxVal; i++ {
		gval[i] = gval[i-1] + fval[i]
	}
}

func query() {
	var q, n int
	fmt.Fscanln(reader, &q)
	for i := 0; i < q; i++ {
		fmt.Fscanln(reader, &n)
		fmt.Fprintln(writer, gval[n])
	}
}
func main() {
	defer writer.Flush()
	initalize()
	query()
}

 

풀이 완료!