백준 BOJ 17425 - 약수의 합

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

17425번: 약수의 합

약수의 합을 빠르게 구해야 하는 문제.

시간이 좀 타이트하니 fastio를 사용해주자.

 

약수의 합 f[i] 를 빠르게 구하기 위한 소스코드이다.

나눗셈 연산, 나머지 연산은 계산 속도가 좀 느린편이라

속도를 빠르게 하기 위해서 제일 기본적인 덧셈 연산만 사용하도록

소스코드를 작성해줘야 한다.

for(ll i=1; i<=1000000; i++){
	for(ll j=i; j<=1000000; j+=i){
		f[j] += i;
	}
}

g[i]를 구하는 부분은

그냥 평범한 prefix sum이다.

for(int i=1; i<=1000000; i++){
	g[i] = g[i-1] + f[i];
}

전체 소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll f[1234567] = {0};
ll g[1234567] = {0};

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	for(ll i=1; i<=1000000; i++){
		for(ll j=i; j<=1000000; j+=i){
			f[j] += i;
		}
	}
	
	for(int i=1; i<=1000000; i++){
		g[i] = g[i-1] + f[i];
	}
	
	int N,k;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> k;
		cout << g[k] << "\n";
	}
	return 0;
}