BOJ-17427번 약수의 합 2

BOJ-백준 17427번 약수의 합 2

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

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)을 구해보자.

 

✅ Python 정답 코드 입니다. 더보기 클릭!

 

import sys
input=sys.stdin.readline
n = int(input())
gn = 0
for i in range(1,n+1):
  gn += i * (n//i)
print(gn)

 

📌 해설

약수의 합을 구하는 함수를 구현합니다.

 

🚩주의

제한시간이 0.5초로 짧기 때문에

 * 1~n 까지 나누어 가면서 나머지가 0인 약수(i)들을 구해서 합하는 방법

( O(n**2))

 * 1~n**(1/2)까지 나누어 가면서 나머지가 0인 약수(i)와 대칭구조를 이루는 (n//i)를 구해서 합하는 방법

(O(n*n**(1/2))

모두 시간 초과됩니다. 

 

g(N)에 대하여 약수 1은 N 개, 약수 2는  N//2개, 약수 3은 N//3개 ... 약수 i 는 N//i개 있음을 확인 할 수 있습니다. 

 

따라서 g(N) = 1*N//1 + 2*N//2 + 3*N//3 + ... + N*N//N 이라고 정의 할 수 있습니다. 

 

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

 

 

참조 : https://enhjh.tistory.com/37

 

::

왜 시간초과인지 엄청 고민했던 문제ㅎ...