백준 2247 실질적 약수 C++

간단한 해설

어떤 자연수 x의 실질적 약수를 찾고, 그 자연수의 실질적 약수들의 합을 구한다. 이를 1부터 n까지 다 더한다.

 

n이 2억이므로 웬만하면 시간복잡도 O(N)만에 끝내야 한다. n의 크기때문에 약수를 구하는 알고리즘으로는 이걸 해결할 수 없다.

 

그러면 이렇게 생각해보자. 어떤 자연수의 실질적 약수를 구하는 것이 아니라, 어떤 자연수의 실질적 약수의 합만 구하면 되는거다.

 

어떠한 자연수 x가 짝수라면 실질적 약수는 2가 포함되어 있을 것이다. 그러면 1부터 n까지 실질적 약수의 합에는
2가 n/2-1 개 들어가 있다. (2의 실질적 약수의 합은 0이기 때문에 n/2-1이다.)

 

어떠한 자연수 x가 3의 배수라면 실질적 약수에는 3이 포함되어 있다. 그러면 1부터 n까지 실질적 약수의 합에는 3이 n/3-1 개 들어가 있다.

 

결국 sigma 1부터 n/2까지 i*(n/i-1)를 하면 된다. (n이 n/2를 넘어가는순간 실질적약수에 포함이 안되기 때문에 제외)

답

간단하다. (백준 서버 이상해서 깃허브 오토 푸시가 안되어서 빨간체크잇음)

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    ll ans=0;
    ll MOD=1000000;
    for(int i=2;i<n;++i){
        if(n/i-1<=0) break;
        ans=(ans+i*(n/i-1)%MOD )%MOD;
    }
    cout<<ans;
}