[BOJ/백준][Gold5] 17425 : 약수의 합 (C++)

https://www.acmicpc.net/problem/17425

17425번: 약수의 합

 

 

[난이도] Gold5
[유형] 수학

[풀이]
1~1000000의 수에 대해 각각의 모든 약수를 구해서 미리 저장해놔야 하는데
일반적으로 루트N에 모든 약수를 구하는 방법으로
각각의 수에 대해 구할 경우 O(루트(1000000))의 복잡도가 필요합니다.
위 방법을 사용할 경우 O(1000000*1000) 의 시간이 걸리므로 시간내에 해결이 불가능합니다.
에라토스테네스의 체를 이용해 소수를 구할때와 비슷한 방식으로
f[1000001] 배열을 미리 선언해놓고 1~1000000까지를 순회하면서
i에 대해 f[i*1],f[i*2],f[i*3].. (i*k <=1000000) 에 i를 더해주면 f 배열을 채울 수 있습니다.
이를 이용해 부분합 배열 s를 만들어 채워주면 쿼리에 대한 답을 O(1)에 구할 수 있습니다.

 

#include <cstdio>
using ll = long long;
int T,f[1000001];
ll s[1000001];
int main(){
    scanf("%d",&T);
    for(int i=1;i<=1e6;i++)
        for(int j=i;j<=1e6;j+=i) f[j]+=i;
    for(int i=1;i<=1e6;i++) s[i]=f[i]+s[i-1]; 
    while(T--){
        int v;
        scanf("%d",&v);
        printf("%lld\n",s[v]);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/17425.cpp