반응형
17425번: 약수의 합
두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
// https://rudruddl.tistory.com/m/524
#include <iostream>
using namespace std;
long long t, n, dp[1000001], sum[1000001];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
/*
1 ~ 1,000,000까지 미리 채워넣음
1은 모든 숫자에 다 포함되기 때문에
i = 2부터 실행하면 1,000,000번 만큼 수행 안해도 됨
*/
dp[1] = 1;
for (int i = 2; i <= 1000000; i++) {
// 나의 배수에게 나를 채워넣음
for (int j = 1; i * j <= 1000000; j++) {
dp[i * j] += i;
}
// 1은 직접 채워줌
dp[i] += (dp[i - 1] + 1);
}
cin >> t;
while (t--) {
int ans = 0;
cin >> n;
cout << dp[n] << '\n';
}
}
|
cs |
반응형