백준 17425 약수의 합

문제 URL : https://www.acmicpc.net/problem/17425

17425번: 약수의 합

문제 접근법 :

100만까지의 약수를 효율적으로 구해서

prefix sum으로 계산하는 문제인줄 알다가 시간초과 나더군요

좀더 효율적인 방법이 필요했는데

에라토스테네스의 체를 좀변형시켜서 해당 약수을 다더하면 되더군요

 

소스코드 :

#include<bits/stdc++.h>
using namespace std;
int test;
vector<long long> v,dp;
void input(){
	cin>>test;
	int a;
	for(int i=0;i<test;i++){
		cin>>a;
		v.push_back(a);
	}
}
void solve(){
	dp=vector<long long>(1000001);
	for(int n=1;n<=1000000;n++){
		for(int j=n;j<=1000000;j+=n){
			dp[j]+=n;
		}
	}
	for(int i=1;i<=1000000;i++)dp[i]+=dp[i-1];
	for(int i=0;i<v.size();i++){
		cout<<dp[v[i]]<<"\n";
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	input();
	solve();
}

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.