[백준/파이썬] 17427 : 약수의 합 2

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

17427번: 약수의 합 2

문제 요약 : 자연수 A의 약수의 합은 f(A)이다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)이다. 자연수 N이 주어졌을 때, g(N)을 구하라.

 

시도 )

# 약수의 합2
import sys
input = sys.stdin.readline

ans = 0
for number in range(1,int(input())+1):
    for i in range(1,round(number**(1/2))+1):
        if number%i == 0 :   # 나누어 떨어짐
            if i*i != number :
                ans += (number//i)
            ans += i

print(ans)

이렇게 풀면 시간 복잡도가 O(n√(n))이 나오게 된다.

이 문제의 경우, N=1,000,000이므로 O(nlogn)보다 시간이 덜 걸려야한다.

(관련 시간 제한 내용)

 

 

풀이 )

2의 배수는 항상 2를 약수로 가진다.

3의 배수는 항상 3을 약수로 가진다.

...

N의 배수는 항상 N을 약수로 가진다.

 

이 개념을 사용하여야 한다.

 

예를 들어 N을 6로 가정해보자.

f(1) = 1

f(2) = 1 + 2

f(3) = 1 + 3

f(4) = 1 + 2 + 4

f(5) = 1 + 5

f(6) = 1 + 2 + 3 + 6

 

1,2,3,4,5,6은 1의 배수이므로 항상 1을 약수로 가진다.

2,4,6은 2의 배수이므로 항상 2를 약수로 가진다.

3,6은 3의 배수이므로 항상 3을 약수로 가진다.

...

 

for 문을 이용하여 1부터 N까지 수를 하나씩 대입한 해보자.

1을 배수로 가지는 수의 개수는 N개이다.

2를 배수로 가지는 수의 개수는 N//2 개이다.

3을 배수로 가지는 수의 개수는 N//3 개이다.

 

이 원리를 이용하면, g(n) = 1*(n//1) + 2*(n//2) . . .+ n*(n//n) 이 됨을 알 수 있다.

이 경우 시간 복잡도는 O(n)이 된다.

# 약수의 합2
import sys
input = sys.stdin.readline

N = int(input())
answer = 0
for number in range(1,N+1):
    answer += (number)*(N//number)

print(answer)