17425 약수의 합
문제
두 자연수 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)를 출력한다.
풀이
에라토스 테네스의 체를 이용해서 INF까지의 숫자들의 약수들의 합을 구해줄 수 있습니다. i가 2라고 예를 든다면 (j가 1~5..)i*j => 2,4,6,8,10 .. 의 dp의 숫자들에 미리 2라는 수를 더해 놓을 수 있습니다.
그리고 문제는 N이하의 모든 약수의 합을 더하는 것이기 때문에 이런식으로 [1,3,4,7,6 -> 1,4,8,15,21 ] 차례대로 이전의 값과 지금의 합을 더해주게 됩니다. 이런식으로 dp를 이용하면 시간초과를 벗어날 수 있습니다.
import sys
sys.stdin = open('input.txt')
input= sys.stdin.readline
INF = 1000000
dp = [0]*(INF+1)
for i in range(1,INF+1): # 1부터 하나씩 모든 약수들을 적는 칸에 추가해준다.
for j in range(1,INF//i+1):
dp[i*j]+=i
for i in range(1,INF+1):
dp[i] += dp[i-1]
T = int(input())
for _ in range(T):
print(dp[int(input())])
Author And Source
이 문제에 관하여(17425 약수의 합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bbnerino/17425-약수의-합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)