ALiNew ALiNew

정수론

• [Algo Rhythm🕺💃] BOJ 17427 - 약수의 합 2

  Algo Rhythm🕺💃/BOJ 2021. 6. 24. 01:42

  문제 분석 입력으로 주어지는 자연수를 $n (1 \le n \le 10^6)$ 그리고 $n$보다 작거나 같은 자연수를 $i$라고 하자. 자연수 $a$가 자연수 $b$로 나누어 떨어진다면 즉, $a$가 $b$의 배수라면 $b$는 $a$의 약수이다. 따라서, 이 문제는 $i$에 속하는 한 자연수의 배수의 개수와 그 자연수를 곱한 값들을 더하여 $g(n) = \sum_{i=1}^n f(i)$을 구하는 문제로 이해할 수 있다. 문제 풀이 $i$를 1부터 $n$까지 반복하여 $i$의 배수의 개수와 $i$를 곱한 값들을 더한다. 이때 $i$의 배수는 $n/i$개이다. 그리고 $i > n/2$일 때 $n$보다 작은 자연수들 중 $i$의 배수는 $i$ 자기 자신뿐이다. 따라서 그 경우에는 $i$만 더한다. 복잡도 분석..

  Read More