17425번: 약수의 합
두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더
www.acmicpc.net
풀이
약수의 합을 미리 구한다.
for(int i = 1; i <= 1000001; i++){
for(int j = i; j <= 1000001; j+=i){
dp[j] += i;
}
}위 식대로 구하게 되면 dp배열에 차례대로 값들이 더해진다. 먼저 i = 1 인 경우에, 백만번 모두 순회하며 1씩 더해준다. 모든 수는 1을 약수로 가지고 있기에 더해도 된다. 마찬가지로 i = 2 인 경우에, 2의 배수씩 증가하면서 모두 순회하며 2를 더해준다. 모든 짝수는 2를 약수로 가지고 있기에 더해도 된다. 다음 i = 3 인 경우에, 3의 배수씩 증가하면서 3의 배수의 모든 수에게 3을 더해준다.
반복문이 끝나면 dp 배열에는 각 index수에 해당하는 약수의 합이 들어있게 된다.
이 문제는 약수의 합을 모두 더한 값을 출력해야한다. 만약 5라면 1의 약수의 합, 2의 약수의 합, 3의 약수의 합... 모든 약수의 합을 다시 구한다.
for(int i = 2; i<= 1000001; i++){
dp[i] += dp[i-1];
}그럼 문제 풀이는 끝이난다.
다만 위와 같이 풀고도, 입출력 함수가 cin, cout을 사용한다면 시간초과가 난다. scanf, printf를 사용해 입출력해주도록 한다.
