https://www.acmicpc.net/problem/17427
약수를 구하는 방법은 총 2가지로 알고 있었다.
1. 자연수 N이 주어졌을 때, 1부터 N까지 나누어가면서 나머지가 0인 값을 구하는 방법 => O(n^2)
2. 자연수 N이 주어졌을 때, 약수는 서로 대칭구조를 이루고 있으므로 1부터 까지의 약수를 구하는 방법 => O(n√(n))
시간제한이 0.5초 이기 때문에 위의 두 방법은 이용할 수 가 없었다.
만약 n이 7일경우
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
f(7) = 1 + 7
'N이하의 자연수 중에서 i를 약수로 갖는 개수는 를 이용한다 개'
import sys
input=sys.stdin.readline
n = int(input())
sum_ = 0
for i in range(1, n+1):
sum_ += (n//i)*i
print(sum_)
'Algorithm > Algorithm Problem' 카테고리의 다른 글
백준 1931 회의실 배정 (0) | 2021.11.16 |
---|---|
백준 6064 카잉 달력 (0) | 2021.11.04 |
##백준 15990 1, 2, 3 더하기5 (0) | 2021.10.29 |
백준 11052 카드 구매하기 (0) | 2021.10.29 |
백준 1406 에디터 (0) | 2021.10.19 |