취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17425번 문제인 약수의 합이다.
문제는 아래 링크를 확인하자.

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

양의 정수 N의 약수들의 합을 구하는 공식은 중학교 교과과정에 나오는 것으로 기억한다.

N의 약수들의 합은 N의 각 소인수 p에 대하여 p의 개수가 k개일 때 (1+p+p^2+p^3+...+p^k)들의 곱으로 구할 수 있다. 해당 식을 전개해보면 N의 모든 약수들이 중복 없이 한번씩 등장하는 것을 확인할 수 있다.

이 문제는 먼저 100만까지의 수들의 약수의 합들을 구해 prefix sum들을 구해두고, 각 N을 입력 받아 바로바로 출력해주는 것으로 문제를 해결할 수 있다.

이 과정에서 가장 작은 소인수를 보관하는 에라토스테네스의 체를 구현하여 소모 시간을 줄일 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int sieve[1000001];
ll query[1000001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 2; i < 1000; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 1000001; j += i) {
			if (sieve[j]) continue;
			sieve[j] = i;
		}
	}

	query[1] = 1;
	for (int NN = 2; NN < 1000001; NN++) {
		ll N = NN;
		if (sieve[N] == 0) {
			query[N] = query[N - 1] + N + 1;
			continue;
		}
		ll ans = 1;
		int current = sieve[N], cnt = 0;
		while (sieve[N]) {
			if (sieve[N] == current) cnt++;
			else {
				ll ret = 0;
				ll temp = 1;
				for (int i = 0; i <= cnt; i++) {
					ret += temp;
					temp *= current;
				}
				ans *= ret;
				current = sieve[N], cnt = 1;
			}
			N /= sieve[N];
		}
		if (N == current) {
			cnt++;
			ll ret = 0;
			ll temp = 1;
			for (int i = 0; i <= cnt; i++) {
				ret += temp;
				temp *= current;
			}
			ans *= ret;
		}
		else {
			ll ret = 0;
			ll temp = 1;
			for (int i = 0; i <= cnt; i++) {
				ret += temp;
				temp *= current;
			}
			ans *= ret;
			ans *= (N + 1);
		}

		query[NN] = query[NN - 1] + ans;
	}

	int x; cin >> x;
	cout << query[x];
}